Есть ли эффективный алгоритм для поиска исходной команды, данной машине Тьюринга, по ее выводу?

Question

У меня очень большая таблица переходов, созданная для машины Тьюринга, которая генерирует строки алфавита в качестве выходных данных. Теперь я пытаюсь создать еще одну машину Тьюринга, которая декодирует выходные данные и находит исходные данные, предоставленные этой машине.

Есть ли эффективный способ отследить правила, чтобы найти вход? Порядок, в котором правила применялись изначально, очень важен, и опробовать каждое возможное правило не было идеальным. Я думал о динамическом программировании, но это все еще занимает огромное количество времени.

Answer 1

Нет.

По крайней мере, не для общего случая, который вы указали.Для конкретной машины Тьюринга, вероятно, есть.

Самый эффективный алгоритм, который я могу придумать, - это грубая сила.Второй наиболее эффективный алгоритм - это нейронная сеть, обученная на машине Тьюринга.Излишне говорить, что оба способа ужасно неэффективны (как во время выполнения, так и в реализации)