2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Машина тьюринга останавливается в некоторых интерпретациях?
Сообщение10.08.2019, 15:47 
Кажется я где-то запутался.

1. Для машины Тьюринга M можно логикой первого порядка и ZF записать предложение, что M при подаче n на вход не останавливается, например что-то вроде <тут аксиомы ZF>→<тут сформулированное в ZF предложение, что M при подаче n не останавливается>
2. Если это предложение верно во всех интерпретациях ZF, то существует его доказательство (по теореме Гёделя о полноте).
3. Если для каждой неостанавливающейся пары (M, n) существует доказатальство предложения вида как в шаге 1, то функция останова вычислима - параллельно делаем: 1 шаг машины тьюринга, один шаг дедуктивного вывода поиском вширь, когда-нибудь или остановится, или мы дойдем доказательство предложения.
4. Значит существует M и n такие, что M не останавливается при n на входе, но в некоторой интерпретации ZF оно останавливается.

Как так?

 
 
 
 Re: Машина тьюринга останавливается в некоторых интерпретациях?
Сообщение10.08.2019, 16:52 
Теория множеств учит, что существуют нестандартные интерпретации, в которых натуральный ряд содержит нестандартные бесконечно большие числа. Где-то там и остановится машина. Ещё вариант: добавим к арифметике аксиому "есть вывод противоречия в арифметике". Эта теория непротиворечива (по второй теореме Гёделя). По теореме о полноте у неё есть модель. Это нестандартный натуральный ряд, в котором есть бесконечно длинный (недостижимый для нас) вывод противоречия.

 
 
 
 Re: Машина тьюринга останавливается в некоторых интерпретациях?
Сообщение10.08.2019, 18:35 
Тогда почему бы не дополнить ZF(C) дополнительными аксиомами, чтобы не было интерпретаций, в которых правдива всякая чушь?

Upd: ах, кажется теорема Геделя о неполноте говорит, что так не получится

 
 
 
 Re: Машина тьюринга останавливается в некоторых интерпретациях?
Сообщение10.08.2019, 23:04 
Аватара пользователя
george66 в сообщении #1409680 писал(а):
Где-то там и остановится машина
Правда ждать этого, сами понимаете, бесконечно долго.

 
 
 [ Сообщений: 4 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group