@Aliksan

Можно ли заранее предугадать (не запустив программу), как закончится любая программа машины Тьюринга?
Варианты:
1. Нет
2. Да, если программа не закрутится в цикл
3. Да, если будет достаточно времени для исполнения программы
4. Да

Помогите, кто знает!

0

@Sindbad_M

2 и 4 друг другу не противоречат, оба правильные.

1

@Aliksan

Но может все таки 2 более правильный? Я вообще считал, что нет. Спасибо за ответ!

0

@Sindbad_M

зависит от контекста. Что называть "предсказать как закончится"?
Предсказать что программа при определенных условиях завершится или зациклится (никогда не завершится) можно для любой программы. Какой ответ кажется вам наиболее верным для программы на Паскале или С++, тот же и будет для машины Тьюринга.

1

@3D Homer

Нельзя, даже если ее запустить.

Если спрашивается, бывают ли программы, по тексту которой можно определить, остановится ли она, то ответ, естественно, да. Если спрашивается, существует ли общий способ по тексту любой программы (запуская ее или нет) определить за конечное время, остановится ли она, то ответ нет, не существует (проблема останова неразрешима). Пункт 2 вообще странный: войдет ли программа в бесконечный цикл — это как раз та информация, которую по тексту программы в общем случае определить невозможно. Если кто-то дает эту информацию сверхъестественным образом, то это меняет дело. В таком случае нужно точно определить, что значит "закрутится в цикл".

Вообще практически никакое свойство программы неразрешимо (нельзя сказать за конечное время, да или нет): теорема Райса.

0