I have a very high dimensional transition table built for a Turing machine which generates alphabet strings as outputs. Now, I'm trying to make another Turing machine that decodes the output and finds the original input given to the machine.

Is there any efficient way to trace down the rules to find the input? The order in which the rules were applied initially is very important and trying out every possible rule was not ideal. I've thought of doing dynamic programming but this still takes a huge amount of time.

1 Answers

wotanii On


At least not for the general case you have stated. For a specific Turing machine, there probably is.

The most efficient algorithm I can think of is brute force. The second most efficient algorithm is a neural net trained on a Turing machine. Needless to say both ways are horribly in-efficient (both in runtime and in implementation)