Лекция: Гипотеза Поста.
Назовем числовым кортежем (или просто кортежем) упорядоченный набор чисел произвольной длины. Под длиной кортежа будем понимать количество чисел, входящих в него. Так кортеж {2, 2, 3, 6} имеет длину 6.
Пусть каждому исходному данному из N (множество числовых кортежей) либо ничего не поставлено в соответствие, либо поставлено в соответствие некоторое (вообще говоря, свое для каждого исходного данного) результирующее число. Тогда можно рассмотреть две задачи: Задача (П). Составить программу МП, перерабатывающую любое исходное данное, для которого есть результирующее число, в это число, и не приводящую ни к какому результату для исходного данного, для которого нет результирующего числа.
Задача (А). Получается из задачи (П) заменой слов «программа МП» на «алгоритм».
Гипотеза Поста:Задачи (А) и (П) одновременно либо имеют, либо не имеют решения.
Очевидно, что гипотеза Поста состоит из двух утверждений:
1. из разрешимости задачи (П) следует разрешимость задачи (А);
2. из разрешимости задачи (А) следует разрешимость задачи (П).
Появление теории МТ и МП привело к следующим результатам:
· Началось развитие более общей теории воображаемых машин — теории автоматов
· Была доказана алгоритмическая разрешимость большого класса задач в математике
· Удалось доказать алгоритмическую неразрешимость некоторых задач в математике.