Гипотеза Поста

Назовем числовым кортежем (или просто кортежем) упорядоченный набор чисел произвольной длины. Под длиной кортежа будем понимать количество чисел, входящих в него. Так кортеж {2, 2, 3, 6} имеет длину 6.

Пусть каждому исходному данному из N (множество числовых корте­жей) либо ничего не поставлено в соответствие, либо поставлено в соот­ветствие некоторое (вообще говоря, свое для каждого исходного данного) результирующее число. Тогда можно рассмотреть две задачи: Задача (П). Составить программу МП, перерабатывающую любое ис­ходное данное, для которого есть результирующее число, в это число, и не приводящую ни к какому результату для исходного данного, для которого нет результирующего числа.

Задача (А). Получается из задачи (П) заменой слов «программа МП» на «алгоритм».

Гипотеза Поста: Задачи (А) и (П) одновременно либо имеют, либо не имеют решения.

Очевидно, что гипотеза Поста состоит из двух утверждений:

1. из разрешимости задачи (П) следует разрешимость задачи (А);

2. из разрешимости задачи (А) следует разрешимость задачи (П).
Появление теории МТ и МП привело к следующим результатам:

· Началось развитие более общей теории воображаемых машин - тео­рии автоматов

· Была доказана алгоритмическая разрешимость большого класса за­дач в математике

· Удалось доказать алгоритмическую неразрешимость некоторых задач в математике.