You can't just request arbitrary Bitcoin node to perform specific computation just for you.
Technically you can, the question is rather "should you", or even "do you have enough coins to pay for it". Because it is possible to use binary gates, by pushing OP_TRUE or OP_FALSE on the stack, and a NAND gate can be done with just "OP_ADD OP_2 OP_EQUAL OP_NOT". Of course, there are more complex opcodes, which can be used for many computations, to not wire everything with single bits, but in general, if the size of the Script is infinite, then it can perform arbitrary computations (and when a given Script is too long, then it can be splitted between many transactions, and the chain of scripts can be protected by pre-signed transactions with a shared N-of-N multisig Schnorr signature, which would take 64 bytes).
Also, pegging in any decentralized sidechain to the Bitcoin network is now possible, by using Proof of Work on top of DER signatures. Then, the merkle tree of the next network state can be simply turned into private key, and it can be used by any sidechain miner to grind it, and claim the reward, directly in BTC. As long as k-values used in signatures are equal to 1/2, publishing the signature will reveal the private key behind it. But as long as all honest sidechain miners collectively have more power, than any attacker, they can safely broadcast their transactions on-chain, and get them confirmed in 10 minutes, if for example double-spending it will require grinding it for hours or days (they can pick any difficulty they want, to make things tick).