Может ли машина Тьюринга решить, завершена ли формальная модель вычислений?

Question

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

Я думаю, что это неразрешимая проблема, я прав?

Если это неразрешимо, почему мы (как люди) можем решить полноту Тьюринга?

Answer 1

Хмм:-) решение о полноте Тьюринга не имеет решающего значения для определения, является ли мозг человека полным ТМ; можно пройти механические этапы, чтобы определить полноту тьюринга; это не проблема.

Ключевой вопрос заключается в том, является ли человеческий мозг гиперкомпьютерным [1] или гипертурирующим.

Одним из тестов будет ответ "Да" на один из следующих вопросов: может ли человек предсказать, когда машина Тьюринга остановится? (т.е. решить проблему остановки) Или человеческий мозг не подчиняется теореме Райс.

Обычно ответ на оба вопроса будет "Нет" в общем случае, потому что можно представить ТМ с бесконечно длинной лентой и просто прыгающим вокруг, мы никогда не сможем сказать, когда он попадет в клетку, которая говорит ему остановиться.

Кажущаяся способность к гиперкомпьютерной обработке проистекает из того факта, что мы путаем нормальные компьютеры / программное обеспечение / механические процессы и т. Д. С ТМ.

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