Машины Тьюринга. Тезис Тьюринга

Машина Тьюринга – это математическая модель ЭВМ. Она состоит из: 1) бесконечной в обе стороны ленты, разбитой на ячейки. В каждой ячейке записан один из символов алфавита: a , a , …, a . В алфавите всегда существует пустой символ (или пробел), например, a . Для своей задачи каждый берёт свой алфавит.

2) внутренней памяти q , q , …, q - внутренних состояний машины. Какое-то из внутренних состояний конечное (например, q ), какое-то – начальное (например, q ). Для каждой задачи берётся свой набор внутренних состояний, но начальное и конечное состояния существуют всегда. Эти состояния могут и совпасть.

3) управляющей головки, двигающейся в обе стороны вдоль ленты в дискретные моменты времени. Головка читает символы алфавита, анализирует их, записывает новые символы и двигается по ленте по программе. В зависимости от внутреннего состояния в данный момент и от символа на воспринимаемой ячейке, в следующий момент машина переходит в новое состояние, записывает на ячейку новый символ. Попав в конечное состояние, машина прекращает работу.

Конфигурация на ленте состоит из: 1) последовательности a , a , …, a символов алфавита на ленте. Считается, что в обе стороны ленты бесконечное количество пустых символов и их писать не обязательно. 2) внутреннего состояния q . 3) номера воспринимаемой ячейки.

Если, находясь в данный момент во внутреннем состоянии q и читая с ячейки a , в следующий момент машина переходит в состояние q , пишет на ленте a и двигается по ленте, то это будет команда: q a q a S, где S={L, R, C} (влево, вправо, стоп). При этом машина одну конфигурацию переводит в другую.

Программа – это совокупность всех команд, выполняемых машиной. Каждая программа должна содержать не более одной команды для каждого набора q a , начинающуюся словами q a . Если известно, что какой-то набор q a никогда не реализуется, то команду с ним можно не писать. Порядок команд в программе произволен.

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

Пример: функция f(x)=2 x. Ставим головку на самый левый не пустой символ, если он есть. Числа x ограничены сверху числом t (x <= t).

q / q / R q - память о 1 (единице)

q 0 q 0 C 2 0=0

q 0 q 0 C стоп

q / q / R q - память о 2 (двойке)

……………..

q / q / R q - память о t

q 0 q / R q - память, что надо дописать ещё (t-1) палок

q 0 q / R q - память, что надо дописать ещё (t-2) палок

……………..

q 0 q / R q - память, что надо дописать ещё одну палку

q 0 q / C всё дописано

q / q / C стоп

q 0 q / R

q 0 q / R

……………..

q 0 q / R

q 0 q / C

Команда с левой частью q / отсутствует, так как числа x не превышают числа t. Здесь q - это начальное состояние машины. Первая половина программы (с памяти о 1 до памяти о t) – это блок чтения. Вторая половина программы – это блок записи и остановки. Вся программа целиком выполняется только тогда, когда на ленте записано число t (t палок). Если записано меньшее число, то часть команд не выполняется.

Тезис Тьюринга: всякий алгоритм может быть реализован с помощью

некоторой машины Тьюринга. Без доказательства.

24. Правило перехода к равносильным формулам в логике предикатов: перенос квантора через отрицание.

Укажем несколько правил перехода от одних формул к другим, им равносильным (во всех интерпретациях). Для формул ЛП сохраняются все равносильности и правила равносильных преобразований логики высказываний. Кроме того, существуют следующие правила:

1. Перенос квантора через отрицание. Пусть A – формула ЛП, содержащая свободную переменную x. Тогда справедливы равносильности

( x) A(x) ( x) A(x);

( x) A(x) ( x) A(x).

Поскольку кванторов всего два, то можно считать их противоположными друг другу. Тогда это правило можно формулировать и так: при переносе квантора через отрицание он меняется на противоположный. Сначала докажем первую равносильность.

Пусть x1, …, xn множество (быть может, пустое) всех свободных переменных формулы A, отличных от x. Это же множество является списком всех свободных переменных рассматриваемой равносильности. Докажем, что на любом наборе <a1, …, an> левая и правая части равносильности принимают одинаковое значение.

Пусть переменная x = a. Возможны два случая:

1) для любого элемента a формула A(a, a1, …, an) = 1;

2) для некоторого элемента a0 формула A(a0, a1, …, an) = 0.

В первом случае для любого элемента a формула A(a, a1, …, an) =0. Отсюда по определению ( x) A(x) = 0. С другой стороны, в этом случае ( x) A(x) = 1 и ( x) A(x) = 0.

Во втором случае для элемента a0 формула A(a0, a1, …, an) =1. Отсюда ( x) A(x) = 1. С другой стороны в этом случае ( x) A(x) = 0 и ( x) A(x) = 1.

Докажем теперь вторую равносильность. Применим доказанную первую равносильность в формуле A(x). Тогда ( x) A(x) ( x) A(x) ( x) A(x), и применив равносильность 11 основных равносильностей логики высказываний, получим ( x) A(x) ( x) A(x) ( x) A(x).

25. Правило перехода к равносильным формулам в логике предикатов: вынос квантора за скобки.

Укажем несколько правил перехода от одних формул к другим, им равносильным (во всех интерпретациях). Для формул ЛП сохраняются все равносильности и правила равносильных преобразований логики высказываний. Кроме того, существуют следующие правила:

1. Перенос квантора через отрицание. Пусть A – формула ЛП, содержащая свободную переменную x. Тогда справедливы равносильности

( x) A(x) ( x) A(x);

( x) A(x) ( x) A(x).

Поскольку кванторов всего два, то можно считать их противоположными друг другу. Тогда это правило можно формулировать и так: при переносе квантора через отрицание он меняется на противоположный. Сначала докажем первую равносильность.

Пусть x1, …, xn множество (быть может, пустое) всех свободных переменных формулы A, отличных от x. Это же множество является списком всех свободных переменных рассматриваемой равносильности. Докажем, что на любом наборе <a1, …, an> левая и правая части равносильности принимают одинаковое значение.

Пусть переменная x = a. Возможны два случая:

1) для любого элемента a формула A(a, a1, …, an) = 1;

2) для некоторого элемента a0 формула A(a0, a1, …, an) = 0.

В первом случае для любого элемента a формула A(a, a1, …, an) =0. Отсюда по определению ( x) A(x) = 0. С другой стороны, в этом случае ( x) A(x) = 1 и ( x) A(x) = 0.

Во втором случае для элемента a0 формула A(a0, a1, …, an) =1. Отсюда ( x) A(x) = 1. С другой стороны в этом случае ( x) A(x) = 0 и ( x) A(x) = 1.

Докажем теперь вторую равносильность. Применим доказанную первую равносильность в формуле A(x). Тогда ( x) A(x) ( x) A(x) ( x) A(x), и применив равносильность 11 основных равносильностей логики высказываний, получим ( x) A(x) ( x) A(x) ( x) A(x).