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.
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.
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.
[0] https://en.wikipedia.org/wiki/Hilbert's_tenth_problem