В мета математике Чейтина! В Поисках Омеги он кратко рассказывает о 10-й проблеме Гильберта. Затем он говорит, что любое диофантово уравнение можно заменить на два равных полинома с положительными целыми коэффициентами: .
Затем он говорит, что мы можем думать об этих уравнениях как о «компьютере»:
Компьютер диофантовых уравнений : Программа: , вывод: , время:
С левой стороны , правый боковой . Он говорит, что - программа этого компьютера, которая выводит . Он также говорит, что неизвестные являются многомерной переменной времени .
Что смущает меня, так это то, что он говорит, что 10-я проблема Гильберта явно не решаема, если смотреть таким образом. Он в основном говорит «из-за проблемы остановки Тьюринга». Но я не вижу связи (я только начинаю изучать теорию). Я надеялся, что кто-то мог бы более четко объяснить, в чем здесь смысл Чейтина.
Я знаю, что проблема остановки Тьюринга в основном гласит, что вы не можете предсказать, когда программа остановится до того, как она действительно остановится (учитывая ограниченное количество времени). Что такое приложение к 10-й проблеме Гильберта, используя обозначения, изложенные Чейтиным?
источник