Основывается на простейших или выведенных из простейших функциях g и h:
Тогда новая функция может быть выведена по правилу:
Следует отметить, что функция зависит от аргументов, функция зависит от аргументов, функция зависит от аргументов. Иначе говоря, правило примитивной рекурсии позволяет получить n + 1 -местную функцию из n -местной и n + 2 — местной функций.
Пусть некоторая функция задана правилом рекурсии
Нетрудно заметить, что функция , функция
Вычислим значение функции при .
Нетрудно заметить, что функция выполняет сложение двух чисел и .
3. m — оператор (оператор нахождения наименьшего корня у)
Оператор определяет наименьшее значение у, при котором при фиксированном значении. Принято обозначение
(Читается: «наименьшее такое, что »). Аналогично определяется функция многих переменных:
Для вычисления функции существует следующий алгоритм:
1. Вычисляется . Если это значение функции равно нулю, то . Если , то осуществляется переход к следующему шагу.
Машина Тьюринга в двух словах.
2. Вычисляется . Если это значение функции равно нулю, то . Если , то осуществляется переход к следующему шагу. И т. д.
Если окажется, что для всех функция , то функция считается неопределенной.
Дана функция . Необходимо определить при
Функция называется частично рекурсивной, если она получена из простейших функций за конечное число шагов на основе правил подстановки, примитивной рекурсии или m — оператора.
Функция называется примитивно рекурсивной, если она может быть получена из простейших функций за конечное число шагов на основе правил подстановки, примитивной рекурсии.
Функция называется общерекурсивно й, если она частично рекурсивная и всюдуопределенная.
Тезис А. Черча. Если функция является общерекурсивной, то она выполнима, т.е. имеет алгоритм решения.
Если для решения некоторой массовой проблемы известен алгоритм, то для его реализации необходимо лишь четкое выполнение предписаний этого алгоритма. Автоматизм, необходимый при реализации алгоритма, приводит к мысли о передаче функции человека, реализующий алгоритм, машине. Идею такой машины предложил в 1937 году английский математик А. Тьюринг.
Машина Тьюринга включает в себя:
1. Внешний алфавит — конечное множество символов . В этом алфавите в виде слова кодируется та информация, которая подается в машину. Машина перерабатывает информацию, поданную в виде слова, в новое слово. Обычно символ Внешний алфавит — конечное множество символов обозначает пробел.
2. Внутренний алфавит — конечное множество символов . Для любой машины число состояний фиксировано. Два состояния имеют особое назначение — начальное состояние машины, — заключительное состояние (стоп-состояние).
3. Операторы перемещения Т=. Л, П, Н – это символы сдвига «влево», «вправо» и «на месте».
4. Бесконечная лента Бесконечная лента характеризует память машины. Она разбита на клеточки. В каждую клеточку может быть записан только один символ из внешнего алфавита.
Машина Тьюринга. Принцип работы компьютера
5. Управляющая головка. Управляющая головка (УГ) передвигается вдоль ленты и может останавливаться напротив какой-либо клетки, т. е. считывать символ
6. Управляющая головка. Управляющая головка (УГ) передвигается вдоль ленты и может останавливаться напротив какой-либо клетки, т. е. считывать символ.
Рис. 4.1. Функциональная схема машины Тьюринга.
7. Программа машины Тьюринга (Р) — совокупность всех команд, Программа представляется в виде таблицы и называется Тьюринговой функциональной схемой.
| a0 | a1 | a2 | |
| q1 | а0Пq1 | a1Пq1 | a2Лq2 |
| q2 | а1Пq2 | a2Нq0 | a0Нq0 |
Таким образом, машина Тьюринга может быть представлена в виде четверки:
Работа машины Тьюринга:
Информация, хранящаяся на ленте, является набором символов из внешнего алфавита. Начальное состояние управляющей головки характеризуется символом внутреннего алфавита . Работа машины складывается из тактов. В течение любого такта машина Тьюринга осуществляет следующие действия: машина Тьюринга находится во внутреннем состоянии , считывает входной символ и по таблице работы совершает операцию сдвига , переходя в состояние , при этом входное слово заменяется на :
Если в результате операции машина перейдет в состояние , то работа машины останавливается. Если состояние недостижимо, то значит по данному входному слову машина Тьюринга не достигает конечного состояния и алгоритма для данного входного слова не существует.
Построить машину Тьюринга, которая будет стирать последнюю единицу в последовательности единиц.
Внешний алфавит — . Внутренний алфавит -, при этом состояние .сохраняется до тех пор, пока не будет найден конец последовательности единиц, состояние — стирание последней единицы. При этом следует заметить, что ситуация в работе машины Тьюринга невозможна, поэтому соответствующая клеточка доопределена произвольно, например . Начальное состояние на начале последовательности единиц. Рабочая программа машины Тьюринга имеет вид:
Проверим работоспособность машины Тьюринга:
Тезис А. Черча. Если функция выполнима, то она всегда может быть представлена в виде машины Тьюринга.
Источник: studopedia.su
Машина Тьюринга
Машина Тьюринга – это строгое
математическое построение,
математический аппарат, созданный для
решения определённых задач.
Машина Тьюринга – абстрактный исполнитель,
осуществляющий алгоритмический процесс, созданный для
уточнения понятия алгоритма.
Это математический объект, а не физическая машина.
Предложена Аланом Тьюрингом в 1936 году
3. Структура и описание машины Тьюринга
Машина Тьюринга состоит из:
бесконечной ленты, разделенной на ячейки;
каретки (читающей и записывающей головки);
программируемого автомата (программа в виде
таблицы).
Автомат каждый раз “видит” только одну ячейку. В зависимости
от того, какую букву он видит, а также в зависимости от своего
состояния q автомат может выполнять следующие действия:
записать новую букву в обозреваемую ячейку;
выполнить сдвиг по ленте на одну ячейку вправо/влево или
остаться неподвижным;
перейти в новое состояние.
4.
Устройство машины Тьюринга
1) Внешний алфавит
А =
Элемент a0 называется пустой символ или
пустая буква (признак того, что ячейка пуста).
В этом алфавите в виде слова кодируется исходный набор
данных и результат работы алгоритма.
5.
Устройство машины Тьюринга
2) Внутренний алфавит
Q = ,
В любой момент времени машина Тьюринга находится
в одном из состояний q0, q1, …, qm
При этом:
q1 — начальное состояние (машина
начинает работу)
q0 — заключительное состояние
(машина закончила работу)
Символы – символы сдвига (вправо, влево,
на месте)
6.
Устройство машины Тьюринга
3) Внешняя память (лента)
Машина имеет ленту, разбитую на ячейки, в
каждую из которых может быть записана
только одна буква
7.
Устройство машины Тьюринга
3) Внешняя память (лента)
Пустая клетка содержит a0.
В каждый момент времени на ленте
записано конечное число непустых букв
Лента является конечной, но дополняется в любой
момент ячейками слева и справа для записи новых
непустых символов.
Это соответствует принципу абстракции
потенциальной осуществимости
8.
Устройство машины Тьюринга
4) Каретка (управляющая головка)
Каретка машины располагается над
некоторой ячейкой ленты – воспринимает
символ, записанный в ячейке
В одном такте работы каретка сдвигается на
одну ячейку (вправо, влево) или остается на
месте
9.
Устройство машины Тьюринга
5) Функциональная схема (программа)
Программа машины состоит из команд:
Для каждой пары (qi, aj) программа машины
должна содержать одну команду
(детерминированная машина Тьюринга)
10.
Описание работы машины Тьюринга
К началу работы машины на ленту подается
исходный набор данных в виде слова
Будем говорить, что непустое слово в алфавите
А= воспринимается машиной в
стандартном положении, если:
— оно задано в последовательных ячейках ленты,
— все другие ячейки пусты,
— машина обозревает крайнюю правую ячейку из тех, в
которых записано слово
11.
Описание работы машины Тьюринга
Стандартное положение называется
начальным (заключительным), если
машина, воспринимающая слово в
стандартном положении, находится в
начальном состоянии q1 (стоп-состоянии q0)
12.
Описание работы машины Тьюринга
Находясь в не заключительном состоянии,
машина совершает шаг, который
определяется текущим состоянием qi и
обозреваемым символом aj
13.
Описание работы машины Тьюринга
В соответствии с командой qiaj qkal Х
выполняются следующие действия:
1) Содержимое обозреваемой ячейки aj стирается и
в нее записывается символ al (который может
совпадать с aj)
2) Машина переходит в новое состояние qk (оно
может совпадать с состоянием qi)
3) Каретка перемещается в соответствии с
управляемым символом Х
14.
Описание работы машины Тьюринга
При переходе машины в заключительное
состояние q0 ее работа прекращается
На ленте записан результат работы
алгоритма – слово в алфавите А
15.
Машинным словом (конфигурацией)
машины Тьюринга называется слово вида
1qkal 2, где 1 и 2 — слова в алфавите А.
16.
Конфигурация 1qkal 2 интерпретируется
следующим образом:
— машина находится в состоянии qk
— каретка обозревает на ленте символ al
— 1 и 2 – это содержимое ленты до и после
символа al
17.
Применение машин Тьюринга к словам
П р и м е р 1. Дана машина Тьюринга с внешним алфавитом
А = (здесь 0 — символ пустой ячейки), алфавитом внутренних
18. Виды команд машины Тьюринга
1.
2.
3.
Написать новую букву в обозреваемую ячейку
Выполнить сдвиг по ленте на одну ячейку
вправо/влево или остаться на месте (П, Л, C)
Перейти в новое состояние.
а0
q0
q1
а1
…
аi
1 1 1 * 1 1
…
аj
Указание о
смене символа
…
ak qm
qi
…
qj
Указание о
сдвиге каретки
Указание о
смене
внутреннего
состояния
19.
20.
Пример
Дана машина Тьюринга с внешним
алфавитом А = , алфавитом
внутренних состояний Q = , и
следующей функциональной схемой:
Применить машину Тьюринга к слову =11*1,
начиная со стандартного начального
положения
21.
22.
Решение
1) Заменяем содержимое
обозреваемой ячейки 1 на а0
23.
Решение
2) Машина переходит в новое
состояние q2
24.
Решение
3) Каретка перемещается
влево
25.
Решение
Полное подробное
решение
26.
Решение
Полное подробное
решение
27.
Решение
Полное подробное
решение
28.
Решение
Решение, записанное с помощью конфигураций
(в строчку)
29.
= 1*11
Ответ: = 111
30.
Люди могут вести себя по-разному в
одинаковых ситуациях, и этим они
принципиально отличаются от
машин.
31.
Примеры машин Тьюринга
32.
33.
34.
35.
36.
37.
38.
39.
40.
Композиция машин Тьюринга
Определение
Пусть заданы машины Тьюринга
имеющие
общий внешний алфавит
и алфавиты
внутренних состояний
соответственно.
Композицией (или произведением) машины
на
машину
называется новая машина
(которая обозначается
) с тем
же внешним алфавитом
,
алфавитом внутренних состояний
и программой, получающейся следующим образом.
41.
42.
43.
44.
45.
Вычислимые по Тьюрингу функции
46.
По исходному алгоритму переработки слов
можно построить алгоритм для
вычисления соответствующей функции;
в этом случае
такие функции называются алгоритмически
(или эффективно) вычислимыми.
Возникает вопрос о соотношении между
классом
алгоритмически вычислимых функций и
классом функций, вычислимых на машинах
Тьюринга.
Совпадают ли эти классы?
47.
Вычислимость функций на машине Тьюринга
Определение
Функция называется вычислимой по
Тьюрингу, или вычислимой на машине
Тьюринга, если существует машина
Тьюринга, вычисляющая её,
т.е. такая машина Тьюринга, которая вычисляет
её значения для тех наборов значений аргументов, для
которых функция определена, и работающая вечно, если
функция для данного набора значений аргументов не
определена.
48.
Остаётся договориться о некоторых условностях
Во-первых,
речь идёт о функциях (или возможно о частичных
функциях, т.е. не всюду определённых), заданных на
множестве натуральных чисел и принимающих также
натуральные значения.
Во-вторых,
нужно условиться:
как записывать на ленте машины Тьюринга
значения
аргументов функции
из какого положения начинать переработку
исходного слова
в каком положении получать значение функции.
49.
Это можно делать следующим образом:
Значения
аргументов будем
располагать на ленте в виде следующего
слова:
50.
Начинать переработку данного слова будем из
стандартного начального положения
Если функция
определена на
данном наборе значений аргументов, то в
результате на ленте должно быть записано
подряд
единиц;
в противном случае машина должна
работать бесконечно.
При выполнении всех перечисленных условий
будем говорить, что машина Тьюринга
вычисляет данную функцию.
Таким образом, сформулированное определение
становится абсолютно строгим
51.
Правильная вычислимость
функций на машине Тьюринга
Определение
Будем говорить, что машина Тьюринга
правильно вычисляет функцию
если начальное слово
она
переводит в слово
и
при этом в процессе работы не пристраивает к
начальному слову новых ячеек на ленте ни
слева, ни справа.
Если же функция
не определена на данном
наборе значений аргументов, то, начав работать из
указанного положения, она никогда в процессе
работы не будет надстраивать ленту слева.
Источник: ppt-online.org
Лекция № 3. Машины Тьюринга
В состав любой машины Тьюринга входит бесконечная в обе стороны лента, разделенная на ячейки, и головка, способная передвигаться вдоль ленты вправо и влево (см. рис. 4).
Рис. 4. Представление машины Тьюринга.
В ячейку ленты может быть записана буква из алфавита A =0, a1, a2, … an>. Для каждой машины Тьюринга этот алфавит, называемый внешним, вообще говоря, свой. Но принято резервировать символ a0 для обозначения пустой ячейки при определении внешнего алфавита любой машины. Будем также считать, что непустое слово в алфавите A–0> воспринимается любой машиной в стандартном положении, если головка находится напротив крайней справа ячейки ленты из тех, в которых записано слово[5] (см. рис. 5).
Рис. 3. Стандартное положение в машине Тьюринга
(внешний алфавит A =0, 0,1>)
Работа любой машины Тьюринга осуществляется дискретным образом – шагами (тактами). В каждом такте головка располагается напротив какой-либо ячейки, «обозревая» ее. При этом она может «читать», имеющуюся в ячейке букву; записать в ячейку букву (из алфавита A),предварительно стерев старую; сдвигаться на одну ячейку влево или вправо.
Полагается, что при каждом такте работы машина находится в каком-то состоянии, обозначаемом буквой qi из алфавита внутренних состояний – Q =0, q1, q2, ….qm>. Каждая машина Тьюринга имеет свой собственный алфавит внутренних состояний, но принято считать, что символом q0 в таком алфавите обозначается состояние остановки, а символом q1 – начальное состояние. Из состояния q1 машина начинает работать, а попав в состояние q0, прекращает работу.
Работа любой машины Тьюринга осуществляется по своей собственной программе или в соответствии с функциональной схемой, представляющей собой совокупность выражений T(i, j) (1£i£m, 0£j£n, i,jÎZ), именуемыми командами, каждаяиз которыхможет иметь следующий вид (см. таблицу 1).
Функциональная схема машины Тьюринга (программа) может быть записана в виде последовательности команд или в виде таблицы (см. пример 3.1.1).
Таким образом, та или иная машина Тьюринга полностью определяется:
а) внешним алфавитом A =0, a1, a2, … an>;
б) алфавитом внутренних состояний Q =0, q1, q2, ….qm>;
в) программой (функциональной схемой).
| Команды машины Тьюринга | |
| Формат команды | Описание команды |
| qiaj →qkapЛ | В ячейке, которую «обозревает» головка, стирается буква aj. Вместо нее в эту ячейку записывается буква ap. Из состояния qi машина переходит в состояние qk. Головка сдвигается на одну ячейку влево (Л). |
| qiaj →qkapП | В ячейке, которую «обозревает» головка, стирается буква aj. Вместо нее в эту ячейку записывается буква ap. Из состояния qi машина переходит в состояние qk. Головка сдвигается на одну ячейку вправо (П). |
| qiaj → qkap | В ячейке, которую «обозревает» головка, стирается буква aj. Вместо нее в эту ячейку записывается буква ap. Из состояния qi машина переходит в состояние qk. Головка остается на месте. |
Говорят, что слово a перерабатывается машиной Тьюринга в слово b, если от слова a, воспринимаемого в начальном состоянии q1, машина после выполнения конечного числа команд программы приходит к слову b, воспринимаемому в положении остановки.
Пример 3.1.1. Машина Тьюринга определяется функциональной схемой в виде следующей таблицы:
| Q A | q1 | q2 | q3 |
| a0 | q31П | q1a0Л | |
| q2a0Л | q21Л | q31П | |
| * | q0a0 | q2*Л | q31*П |
Слово, воспринимаемое в начальном состоянии q1 имеет вид:
Определим, в какое слово переработает это слово машина.
Так машина находится в состоянии q1 , обозревая ячейку в которой находится 1, то первой должна быть выполнена команда, стоящая на пересечении столбца q1 и строки 1 функциональной схемы. Это команда q2a0Л. После ее выполнения машина перейдет в следующее состояние:
| * | a0 | q2 |
После выполнения следующей команды q2*Л (записанной на пересечении столбца q2 и строки 1) машина перейдет в следующее состояние:
| * | a0 | q2 |
На пересечении столбца q2 и строки 1 в функциональной схеме машины Тьюринга записана команда q21Л, выполнение которой приведет к состоянию:
| * | a0 | q2 |
Полагая, что принцип работы с функциональной схемой машины Тьюринга изложен выше достаточно понятно, далее будем указывать только команды и результат их выполнения.
| * | a0 | q2 |
| * | a0 | q3 |
| * | a0 | q3 |
Источник: studopedia.ru