Машина Поста и машина Тьюринга

Проблема 2: Вычисление совершенных чисел;

Совершенные числа – это числа, которые  равны сумме своих делителей, например: 28 = 1+2+4+7+14.

Определим функцию S(n) = n-ое по счёту совершенное число  и поставим задачу вычисления S(n) по произвольно заданному n. Нет общего метода вычисления совершенных чисел, мы даже не знаем, множество совершенных  чисел конечно или счетно, поэтому  наш алгоритм должен перебирать все  числа подряд, проверяя их на совершенность. Отсутствие общего метода решения не позволяет ответить на вопрос о останове алгоритма. Если мы проверили М чисел  при поиске n-ого совершенного числа  – означает ли это, что его вообще не существует?

Проблема 3: Десятая проблема Гильберта;

Пусть задан  многочлен n-ой степени с целыми коэффициентами – P, существует ли алгоритм, который  определяет, имеет ли уравнение P=0 решение  в целых числах?

Ю.В. Матиясевич показал, что такого алгоритма не существует, т.е. отсутствует общий  метод определения целых корней уравнения P=0 по его целочисленным  коэффициентам.

б) Информационная неопределенность задачи

Проблема 4: Позиционирование машины Поста на последний  помеченный ящик;

Пусть на ленте  машины Поста заданы наборы помеченных ящиков (кортежи) произвольной длины  с произвольными расстояниями между  кортежами и головка находится  у самого левого помеченного ящика. Задача состоит установке головки  на самый правый помеченный ящик последнего кортежа.

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

в) Логическая неразрешимость (в смысле теоремы  Гёделя о неполноте)

Проблема 5: Проблема "останова" (см. теорема);

Проблема 6: Проблема эквивалентности алгоритмов;

По двум произвольным заданным алгоритмам (например, по двум машинам Тьюринга) определить, будут  ли они выдавать одинаковые выходные результаты на любых исходных данных.

Проблема 7: Проблема тотальности;

По произвольному  заданному алгоритму определить, будет ли он останавливаться на всех возможных наборах исходных данных. Другая формулировка этой задачи –  является ли частичный алгоритм Р  всюду определённым?

 

2.7 Заключение

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

Задачи можно  разбить на классы в соответствии со сложностью их решения. Вот важнейшие  из них и предполагаемые соотношения  между ними:

P<=NP<=EXPTIME

Находящийся слева класс P включает все задачи, которые можно решить за полиномиальное время. В класс NP входят все задачи, которые можно решить за полиномиальное время только на недетерминированной  машине Тьюринга (это вариант обычной  машины Тьюринга, которая может делать предположения). Такая машина предполагает решение задачи – либо “удачно  угадывая”, либо перебирая все предположения  параллельно – и проверяет  свое предположение за полиномиальное время.

Класс NP включает в себя класс P, поскольку любую  задачу, решаемую за полиномиальное время  на детерминированной (обычной) машине Тьюринга, можно решить и на недетерминированной  за полиномиальное время, просто этап предположения опускается.

Если все  задачи класса NP решаются за полиномиальное время и на детерминированной  машине, то P=NP. Тем не менее, никем  не доказано, что P<>NP (или P=NP). Однако, большинство специалистов, занимающихся теорией сложности, убеждены, что  это классы неравны.

Как ни странно, можно доказать, что некоторые NP-задачи настолько же трудны, что и любая  задача этого класса. Такие задачи называются NP-полными. То есть, если такая  задача решается за полиномиальное время, то P=NP.

 

2.8 Пример работы машины Тьюринга

Допустим, на ленте есть слово, состоящее из символов #, $, 1 и 0. Требуется заменить все символы # и $ на нули. В момент запуска головка находится над  первой буквой слова слева. Завершается  программа тогда, когда головка  оказывается над пустым символом после самой правой буквы слова. 
Примечание: длина слова и последовательность символов значения не имеют. На рисунке приводится пример последовательности выполнения команд для конкретного случая. Если на ленте будет другое слово, то и последовательность выполнения команд будет другой. Несмотря на это, данная программа для машины Тьюринга (на рисунке – таблица слева) применима к любым словам описанного внешнего алфавита (соблюдается свойство применимости алгоритма ко всем однотипным задачам – массовость).

 

 

 

 

 

 

 

 

 

 

 

 

Можно усложнить  программу. Допустим, головка располагается  не обязательно над первым, а над  любым символом слова. Тогда программа  для данной машины Тьюринга может  быть такой (а могла бы быть и другой):

 

 

 

 

Здесь происходит сдвиг головки влево до тех  пор, пока она не окажется над пустым символом. После этого машина переходит  в состояние q₂ (команды которого совпадают с командами q₁ предыдущей программы).

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Список литературы 
 

1. Колмыкова Е.А., Кумскова И.А.  Информатика: учебной пособие  для студ. сред. проф. образования.  – 2-е изд., стер. – М.: Издательский  центр «Академия», 2009. – 416 с. 
2. Михеева Е.В., Практикум по информатике. – М.: Издательский центр «Академия», 2008. 
3. Михеева Е.В., Информационные технологии в профессиональной деятельности. – М.: Издательский центр «Академия», 2008. 
4. Безручко В.Т. Информатика (курс лекций): учебное пособие. – М.: ИД «Форум»: ИНФРА-М, 2007. – 432.: ил. 
5. Шауцукова Л.З. Учебное пособие для 10-11 кл. общеобразоват. учреждений. – 4-е изд. – М.: Просвещение, 2008. – 416 с.: ил. 
6. Симонович С.В., Евсеев Г.А.Алексеев А. Н. Общая информатика. Учебное пособие для средней школы. – М.: АСТ–Пресс: Инфорком–Пресс, 2007 
7. Информатика: Базовый курс/ Симонович С.В.и др. – СПб.: Питер, 2008

8. http://www.inf1.info/machinepost