Машина Тьюринга, которая не принимает - как мы можем это знать?

Question

Предположим, у меня есть TM M, который принимает язык L. Если я дам ему входное слово w и захочу узнать, принимает ли он его или нет, - могу ли я утверждать, не объясняя, что я делаю, если M НЕ принимает w?

Я имею в виду - фраза "если М не принимает w" предполагает, что каждый алгоритм неявно способен идентифицировать бесконечный цикл.

Я вижу это много в проблемах сводимости, где M является внутренней TM в алгоритме, который использует принятия M, а также непринятие M, и я никогда не видел объяснения, как внешний алгоритм может узнать, что M не принял. Просто сказано - "если М принимает.... еще....", как алгоритм может обнаружить "еще" часть? В случае бесконечного цикла, как это обнаруживается?

Спасибо

Answer 1

Как правило, вы не можете обнаружить алгоритмически, что TM не останавливается на данном входе.

Для проблем "если М принимают... еще...." одна возможность состоит в том, что другая часть всегда приводит к неприятию. В этом случае не имеет значения, будет ли внутренняя ТМ петля или нет. Если это произойдет, внешний также будет зацикливаться и не принимать. Поэтому остальная часть не должна быть выполнена.

Другой возможный случай - вы смотрите только на рекурсивные / разрешимые языки во внутренней ТМ. Тогда вы всегда получите ответ.