[DonbunEf7]

Sure. For example, you might specify a contract which happens to require a solution to a Diophantine equation be generated for a certain handful of coefficients. This is known to scale up in complexity to Turing-completeness. [0] An example equation might govern the exchange or transfer of some resources, in which the contract only accepts a resource exchange which is equivalent in value.

[0] https://en.wikipedia.org/wiki/Hilbert's_tenth_problem

[dynamic]

Even in this... implausible scenario, the contract would only need to verify the solution to the equation. The party creating the transaction would then be responsible for generating a solution.

[firethief]

A broadcast-ledger type currency requires every node to agree on the outcome of running transaction scripts. This is very impossible if running scripts is undecidable.