the Taproot update dropped the restrictions for script sizes, so in theory a TX can now have a script with millions of instructions. While exploring the new possibilities I noticed that we can apply to Bitcoin Script a programming concept from zero-knowledge proofs named nondeterministic programming. Whenever possible, the prover computes the result of an expensive operation and then gives that result to the verifier, who only verifies the correctness of the result, which is often much more efficient than computing it.

For example, we can represent integer division efficiently in Bitcoin Script if the result is given to us in the unlocking script. This is because multiplication with a constant is relatively cheap.

Here is a most simple example implementing integer division by 2. We use that multiplication by 2 is simply OP_DUP OP_ADD, which is cheap.

```

# Integer division by 2 with the help of a hint
# In this example, we divide 119 by 2.
# In the unlocking script the prover provides the result
# as a hint 119//2 = 59, which we verify.

btcdeb "[ 

  119             # Some arbitrary input is on the stack
  OP_OVER         # Copy the hint to the top of the stack

  OP_DUP OP_ADD   # Multiply the hint by 2
  OP_SUB          # Subtract that from the 119
              

  # Now the remainder should be on the stack
  # We verify that it is exactly 0 or 1
              
  OP_DUP          # Make a copy
  OP_0NOTEQUAL    # Returns 0 if the input is 0. 1 otherwise.
  OP_EQUALVERIFY

# ]" 59           # The hint provided is 59 = 119/2

```

Here you can find more complex examples of opcodes using hints:
https://github.com/coins/bitcoin-scripts/blob/master/composite-opcodes.md#op_2div

Here is even a script for a bitwise rotation of a 32-bit word. It requires about 100 instructions. I think that suggests it might be possible to implement something like sha256 in about 200-300k opcodes.
https://github.com/coins/bitcoin-scripts/blob/master/op_rotate.md

Furthermore, I wondered if it might be possible to implement a ZKP verifier in Bitcoin script. However, that would probably need some hack to make multiplications much cheaper.