lec15
.pdfНа ленте натуральное х будет записываться массивом из х единиц. Числа на ленте будем разделять символом «*», если пустой символ, то это ноль.
Рассмотрим произвольную функцию y=f(x1, x2, … xi, … xn), где xi,y {0} (принимает целое неотрицательное значение).
Функция f(x1, x2, … xi, … xn) называется вычислимой по Тьюрингу, если существует машина Тьюринга, работающая следующим образом: для любой совокупности чисел x1, x2, … xi, … xn, для которых функция f определена, машина Тьюринга, начав работу из начальной конфигурации
q01x1 1x2 1xn,
заканчивает работу конфигурацией
qz1y,
где y=f(x1, x2, … xi, … xn), 1k – запись числа k в виде k единиц на ленте. Если f на совокупности x1, x2, … xi, … xn не определена, то машина Тьюринга работает бесконечно.
11
Пример 15.1. МТ, вычисляющая y=x+1.
Требуется построить МТ, которая прибавляет единицу к числу на ленте. а) классическая запись чисел, б) x – целое десятичное число: состоит из
цифр, записанных в последовательные ячейки на ленте. |
□ |
1 |
|
||
Решение а): q1 – состояние изменения цифры. |
q1 1qzS |
1q1R |
Решение б): МТ прибавляет 1 к последней цифре числа. Если последняя цифра равна 9, то ее заменить на 0 и прибавить 1 к предыдущей цифре.
|
□ |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
|
|
|
|
|
|||||||
q0 |
q1L |
0q0R |
1q0R |
2q0R 3q0R 4q0R 5q0R 6q0R 7q0R 8q0R 9q0R |
|||||||
q1 |
1qzS |
1qzS |
2qzS |
3qzS 4qzS 5qzS 6qzS 7qzS 8qzS 9qzS 0q1L |
|||||||
q1 – состояние изменения цифры, q0 – ход к последней цифре. Если в состоянии q1 автомат видит цифру 0..8, то заменяет ее на 1..9, соответственно, и переходит в состояние qz. Если же он видит цифру 9, то заменяет ее на 0, сдвигается влево, оставаясь в состоянии q1. Так продолжается до тех пор, пока автомат не встретит цифру меньше 9. Если же все цифры были равны 9, то он заменит их нулями, запишет 0 на месте старшей цифры, сдвинется влево и в пустой клетке запишет 1. Затем
перейдет в состояние qz, т.е. остановится. |
12 |
Вычислимость суперпозиции.
Пусть заданы две функции: y=f(x) и z=g(y), причем z определена на области значений функции f, тогда функция z=g(f(x)) называется
суперпозицией функций f и g или композицией.
Теорема 15.1. Если функции f и g вычислимы по Тьюрингу, то их суперпозиция тоже вычислима по Тьюрингу.
Машину Т=Тf•Тg называют композицией исходных машин Тьюринга.
Доказательство:
Чтобы написать программу для композиции, надо объединить обе программы и сделать следующие изменения: во всех командах первой программы для функции f, где встречается заключительное состояние, его надо заменить на начальное состояние второй программы для функции g.
Пример 15.2. Композиция МТ f и g. |
|
|
|
|
|
|
□ |
1 |
|
||
Для примера 15.1 а). f(x)=x+1, g(x)=g() – |
|
|
|||
|
|
|
|
||
q1 |
1q2S |
1q1R |
|
||
окончание работы в правильной конфигурации. |
|
||||
q2 |
1qzS |
1q1L |
|
||
q2 – ход к первой цифре числа. |
13 |
||||
|
|
|
Вычислимость условного перехода (разветвления).
Пусть x1, x2, … xn символы переменных произвольной природы. n-местным предикатом P(x1, x2, … xn) называется высказывание об этих переменных, которое для каждого набора значений переменных либо не определено, либо истинно, либо ложно.
Областью определения предиката Р(x1, x2, … xn) называется совокупность всех наборов x1, x2, … xn, для которых предикат Р (x1, x2, … xn) либо .И., либо .Л.
Областью истинности предиката называется:
{(x1,…,xn) / P(x1,…,xn) = «И»}.
Областью ложности предиката называется:
{(x1,…,xn) / P(x1,…,xn) = «Л»}.
!!! Определения в ТА аналогичны определениям в исчислении предикатов (лекция 11).
14
Характеристическая функция предиката.
Характеристической функцией предиката Р называется функция:
1, если Р (x1, x2, … xn) = .И. |
|||
χp(x1, x2, … xn) = |
, x |
, … x |
) = .Л. |
0, если Р (x |
|||
1 |
2 |
n |
|
Предикат называется вычислимым по Тьюрингу, если его характеристическая функция вычислима. Иногда предикат будем считать вычислимым, если существует МТ приводящая к конфигурации
.И.x1*x2*…*xn,
то есть перед первым аргументом стоит символ .И., если Р(x1, x2, … xn) = .И.
15
Теорема 15.2. Если функция f1(x1,…,xn),f2(x1,…,xn) и предикат P(x1,…,xn) вычисляется по Тьюрингу, то и функция
f1(x1,…,xn) если Р (х1, |
….,хn) = .И. |
||||
f(x1,…,xn) = f |
(x ,…,x ) если Р (х |
1, |
х |
) = .Л. |
|
2 |
1 |
n |
…., n |
|
|
также вычислима по Тьюрингу.
Вычисление функции f(x1,…,xn) приводит к разветвлению вычисления.
Доказательство: докажем, что существует МТ вычисляющая разветвление.
Будем считать что алфавиты состояний исходных машин не пересекаются. Программу искомой машины составим из программ исходных машин внеся изменения только в программу для Машины Тьюринга вычисляющей
предикат. Те команды где есть конечное состояние .И.qzph заменяем на □q01R (то есть машина переходит к программе для вычисления f1, а команды
.Л.qzph заменяем на □q02R (то есть машина стирает значение «ложь», записывает пустой символ и переходит к программе для вычисления f2.
16
Свойства машины Тьюринга как алгоритма.
Дискретность: МТ может перейти к (k+1)-му шагу только после выполнения k-го шага, т.к. именно шаг k определяет, каким будет (k+1)-й шаг.
Элементарность: На каждом шаге в ячейку пишется символ aʹ из алфавита A, выполняется одно действие h {R,L,S}, и МТ переходит в дискретное состояние.
Детерминированность: В каждой клетке таблицы машины Тьюринга записан лишь один вариант входного символа а. Текущее состояние q вместе с а на каждом шаге однозначно определяет результат последовательность шагов решения задачи определена однозначно, т.е. если МТ на вход подают одно и то же входное слово, то выходное слово каждый раз будет одним и тем же.
Результативность: Содержательно результаты каждого шага и всей последовательности шагов определены однозначно, следовательно, правильно написанная МТ за конечное число шагов перейдет в состояние qz, т.е. за конечное число шагов будет получено решение задачи.
Массовость: Каждая машина Тьюринга определена над всеми |
|
допустимыми словами из алфавита. |
17 |
|
Часть 3.
Геделевская нумерация.
Это прием позволяющий любой алгоритм превратить в численный алгоритм, работающий с натуральными числами:
объекты любой природы можно закодировать натуральными числами.
Пусть существует некоторый алфавит А. Рассмотрим все слова языка А*=множество всех слов в алфавите А. Мы хотим все слова α А* перенумеровать так чтобы соответствие между словом α и его номером
N(α) было взаимно-однозначным. Если α = a |
a |
… a , то номер слова это |
1 |
2 |
|
N α = 2 1 · 3 2· · p ,
где ps – простые числа.
Получим некоторое натуральное число, которое называется его геделевским номером. Это сопоставление каждому слову натуральное число называется первичной нумерацией по Гёделю.
19
Вторичная нумерация: есть последовательность слов Π=α1α2…αk, тогда этой фразе взаимно-однозначно можно составить одно натуральное число:
N П = 2N(α1) · 3N(α2) · · pN(αk k),
где pk – простые числа.
С помощью третичной нумерации можно занумеровать любой текст.
Тоже самое можно проделать и с выходным алфавитом. В таком случае алгоритм переводящий входное слово в выходное будет сведен к вычислению некоторой числовой функции.
По Гёделевскому номеру однозначно восстанавливается закодированный объект: всякое натуральное число однозначно разложимо в произведение степеней простых чисел.
20