25.Операции над машинами Тьюринга. Универсальная машина Тьюринга.

Автомат машины Тьюринга в процессе своей работы может выполнять следующие действия:

• Записывать символ внешнего алфавита в ячейку (в том числе и пустой), заменяя находившийся в ней (в том числе и пустой).

• Передвигаться на одну ячейку влево или вправо.

• Менять свое внутреннее состояние.

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

Универсальной машиной Тьюринга называют машину Тьюринга, которая может заменить собой любую машину Тьюринга.

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

26.Понятие алгоритмической неразрешимости. Теорема Райса.

АЛГОРИТМИЧЕСКАЯ НЕРАЗРЕШИМОСТЬ - Понятие математической логики, означающее, что существуют задачи, для решения которых невозможно в принципе построить алгоритм. Для того чтобы доказать алгоритмическую неразрешимость каких-либо задач, необходимо было уточнить понятие алгоритма, сделать его математически строгим. Математически строгие понятия алгоритма существуют. Это машина Поста, машина Тьюринга, нормальный алгоритм Маркова и пр. Доказательства неразрешимости какой-либо задачи, в большинстве случаев, очень сложны. Приведем формулировку классической алгоритмически неразрешимой задачи: десятой проблемы Гильберта. Задано произвольное алгебраическое уравнение с целыми коэффициентами, надо определить, существует ли у данного уравнения решение в целых числах. Через 70 лет после постановки задачи, в 1970 г., математик Ю. Матиясевич (СССР) доказал невозможность разработки алгоритма, который бы решал эту задачу. Ясна практическая ценность введения понятия «алгоритмическая неразрешимость»: задачи, для которых доказана алгоритмическая неразрешимость, не надо и пытаться решать на компьютере.

В теории алгоритмов, теорема Райса гласит, что для любого нетривиального свойства вычислимых функций, определение, вычисляет ли произвольный алгоритм функцию с таким свойством, является алгоритмически неразрешимой задачей. Здесь свойство называется нетривиальным, если существуют и вычислимые функции, обладающие этим свойством, и вычислимые функции, не обладающие им.

Теорема названа в честь американского математика Генри Гордона Райса, доказавшего её в 1951 году в своей докторской диссертации^[1]. Её следует отличать от теоремы Райса-Шапиро, названной в честь Райса и Нормана Шапиро.

27.Проблема остановки - формулировка теоремы и ее доказательство.

Формулировка проблемы остановки:

Пусть у нас есть строка с закодированной функцией A (всё равно на каком языке, это не принципиально). Требуется создать функцию F, которая определит, будет ли функция A выполняться вечно или нет (зависнет или не зависнет).

Естественно, работа A зависит от входных данных D. Соответственно F должна принимать на вход две переменных: код функции A и входные параметры D. А возвращать F(A, D) будет логическое значение: True — A(D) остановится, False — A(D) будет работать вечно.

По сути, F(A, D) должна проанализировать строку.

Доказательство: Неразрешимость проблемы остановки имеет много доказательств. В терминах функций её очень просто доказать от противного.

Допустим, у нас уже есть решение — функция F, которая принимает на вход некую функцию (вернее строку с текстом функции, байт-кодом или иной записью функции) и некие данные и отвечает на вопрос: «остановится ли функция-первый-аргумент, при работе с данными-вторым-аргументом, или будет работать вечно?»

Давайте создадим функцию P(x), такого вида (на C-образном языке):

троку, которая кодирует эту функцию обозначим p. Что будет, если мы вызовем функцию F(p,p)? Возможны два исхода:

• True, если если P останавливается. Но при этом P(p) как раз не останавливается, если F(p,p)=True, то запускается бесконечный цикл.

• False, если P зависает. Но, как не трудно видеть, именно в этом случае P(p) не зависнет.

Мы получили противоречие потому, что наша начальная посылка о существовании магической функции F была не правильной.

Получается, что задача останова неразрешима. Вернее, нельзя написать программу, которая бы решала эту задачу. Иными словами, нельзя написать парсер программного кода, который бы мог оценить, зависнет разбираемый код или нет.

Неразрешимость проблемы остановки была впервые доказана в 1936 году Аланом Матисоном Тьюрингом.