10-я проблема Гильберта и диофантово уравнение Чейтина «Компьютер»?

10

В мета математике Чейтина! В Поисках Омеги он кратко рассказывает о 10-й проблеме Гильберта. Затем он говорит, что любое диофантово уравнение можно заменить на два равных полинома с положительными целыми коэффициентами: .p=0p=0p1=p2

Затем он говорит, что мы можем думать об этих уравнениях как о «компьютере»:

Компьютер диофантовых уравнений : Программа: , вывод: , время:

L(k,n,x,y,z,...)=R(k,n,x,y,z,...)
k n x,y,z,...

С левой стороны , правый боковой . Он говорит, что - программа этого компьютера, которая выводит . Он также говорит, что неизвестные являются многомерной переменной времени .LRkn

Что смущает меня, так это то, что он говорит, что 10-я проблема Гильберта явно не решаема, если смотреть таким образом. Он в основном говорит «из-за проблемы остановки Тьюринга». Но я не вижу связи (я только начинаю изучать теорию). Я надеялся, что кто-то мог бы более четко объяснить, в чем здесь смысл Чейтина.

Я знаю, что проблема остановки Тьюринга в основном гласит, что вы не можете предсказать, когда программа остановится до того, как она действительно остановится (учитывая ограниченное количество времени). Что такое приложение к 10-й проблеме Гильберта, используя обозначения, изложенные Чейтиным?

неуклонный
источник

Ответы:

7

Хороший вопрос. Похоже, вам может понадобиться дополнительная справка по 10-й проблеме Гильберта. Я надеюсь, что это не излишне.

Проблема спрашивает:

Существует ли алгоритм, который с учетом диофантова полинома решает, есть ли установка его переменных, которая делает его равным ?0

Это было решено в 70-х годах как следствие MRDP (также называемого теоремой Матиясевича, если вам хочется ее искать), в котором говорится:

Определите: множество является диофантовым, если на входах существует диофантовы многочлен такой что .DNpk+1D={x|yR+kp(x,y)=0}

Диофантовы множества - это именно те, которые распознаются машинами Тьюринга.

Эта теорема очевидна в одном направлении (каждое диофантово множество распознается машиной Тьюринга - на входе просто попросите вашу машину угадать векторы , оцените и остановите, если / когда вы обнаружите, что ). Это совершенно неочевидно в другом направлении - почему верно, что каждый узнаваемый набор Тьюринга является диофантовым? Схемы кодирования отвратительны, но, поверьте мне, это можно сделать.xyR+kp(x,y)p(x,y)=0

В любом случае, как теорема MRDP решает 10-ю проблему Гильберта? Хорошо...

Ради противоречия давайте представим, что у нас есть алгоритм, который, учитывая диофантовы многочлен , решает, существует ли входной вектор который вызывает .p(y)yp(y)=0

Теперь я собираюсь использовать этот волшебный алгоритм для решения проблемы остановки. Имея машину, я буду использовать отвратительную кодировку диофантовых уравнений, чтобы преобразовать задачу «Останавливается ли на входе ?» в проблему "Имеет ли диофантовы полином набор входов, которые делают его равным ?" Тогда я буду использовать мой волшебный алгоритм для решения этой проблемы, и теперь я решил проблему остановки.Mxp(y|x)0

Конечно, это невозможно, поэтому в действительности не может быть магического алгоритма, который ищет входной вектор, который вызывает . Точно так же не может быть алгоритма, который смотрит на два диофантовых полинома и решает, равны ли они когда-либо. Это то, что говорит Чейтин.p(y)=0

GMB
источник