Математические гипотезы, эквивалентные остановке машины Тьюринга

11

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

Например: Википедия говорит, что в настоящее время неизвестно, существуют ли какие-то нечетные совершенные числа. Поскольку можно решить, является ли данное число идеальным, можно написать машину Тьюринга, которая по очереди проверяет каждое нечетное число и останавливает его, если находит идеальное число. (Эта машина Тьюринга не принимает никаких данных.) Если бы мы знали, останавливается ли эта машина Тьюринга, мы бы знали, верна ли гипотеза, и наоборот.

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

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

Так что мои вопросы

  • Можно ли создать машину Тьюринга, которая останавливается тогда и только тогда, когда гипотеза о двух простых числах верна? (А если так, то как?)
  • Можно ли вообще создать машину Тьюринга, которая останавливается тогда и только тогда, когда какое-то математическое утверждение верно? Может ли эта машина Тьюринга быть построена алгоритмически из формального утверждения?
  • Если это вообще невозможно, есть ли способ классифицировать математические утверждения на то, эквивалентны ли они остановке одной машины Тьюринга или машины Тьюринга с оракулом и т. Д.? Если так, эта классификация разрешима для данного утверждения?
Натаниель
источник
Что значит «правда»? Какие модели мы оцениваем эту истину относительно? Вы должны определить это сначала, я думаю.
Джейк
Я думаю, что все такие машины Тьюринга могут только проверять доказуемость. Даже если вы явно не повторяете истинные утверждения в PE, вы все равно ищете доказательство в другой форме. Разница в том, что существование нечетного совершенного числа, очевидно, не может быть одновременно истинным и недоказуемым, в то время как двойные простые числа могут.
Каролис Юоделе
Любая гипотеза о несчетных множествах не может быть выражена с помощью машин Тьюринга.
Рафаэль

Ответы:

12

На ваш вопрос отвечает арифметическая иерархия . Существование нечетного совершенного числа является заявление, и поэтому вы можете проверить его с помощью Σ 1 машину, которая останавливается тогда и только тогда утверждение верно. Гипотеза о двойном простом выражении является оператором Π 2 , и поэтому вы можете создать TM с доступом к оракулу, который останавливается, если утверждение неверно.Σ1Σ1Π2

В строгом логическом смысле вы всегда можете создать машину Тьюринга, которая останавливается, если выполняется выражение :φ

  1. Если выполнено, возьмите машину, которая останавливается.φ
  2. Если не держится, возьмите машину, которая не останавливается.φ

Чтобы убедиться, что эта конструкция верна, рассмотрите логическую форму вашего утверждения:

Вы можете устранить эту путаницу, задав несколько иные вопросы:

φT,φT привалы,

Что такое набор утверждений такой, что существует машина Тьюринга, которая останавливается на ϕ Φ, если ϕ верна?ΦφΦφ

Σ1

Юваль Фильмус
источник
Спасибо, я думаю, что арифметическая иерархия - это именно то, о чем я просил. Я думаю, что я на самом деле хотел спросить: «Существует ли общая вычислимая функция из (некоторого подмножества) математических операторов для машин Тьюринга, которые не принимают ввода, так что машина, соответствующая данному выражению, останавливается, если утверждение истинно?» Но, конечно, это эквивалентно предложенной вами версии.
Натаниэль
0

е(1)знак равно2е(2)знак равно4е(N+1)знак равное(N)!N2NΘN

S{Икся!знак равноИксК:я,К{1,...,N}}{ИксяИксJзнак равноИксК:я,J,К{1,...,N}}

Икс1,...,ИксN1(Икс1,...,ИксN)мин(Икс1,...,ИксN)е(N)Θ1,...,Θ16

Θ16е(16)+3WNWWW

Θ160'

Аполониуш Тышка
источник