Студопедия
Случайная страница | ТОМ-1 | ТОМ-2 | ТОМ-3
АрхитектураБиологияГеографияДругоеИностранные языки
ИнформатикаИсторияКультураЛитератураМатематика
МедицинаМеханикаОбразованиеОхрана трудаПедагогика
ПолитикаПравоПрограммированиеПсихологияРелигия
СоциологияСпортСтроительствоФизикаФилософия
ФинансыХимияЭкологияЭкономикаЭлектроника

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



Читайте также:
  1. Агрессия как цель действия: гипотеза катарсиса
  2. Гипотеза
  3. Гипотеза
  4. Гипотеза
  5. Гипотеза вторая: против Церкви
  6. Гипотеза геи
  7. ГИПОТЕЗА ГЕИ

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

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

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

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

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

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

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

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

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

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


Дата добавления: 2015-07-11; просмотров: 65 | Нарушение авторских прав






mybiblioteka.su - 2015-2024 год. (0.005 сек.)