- Главная
- Математика
- Универсальная машина Тьюринга. Теоретическая модель современного компьютера
Содержание
- 2. До сих пор мы придерживались той точки зрения, что различные алгоритмы осуществляются в различных машинах Тьюринга,
- 3. Алгоритм подражания Для того чтобы лучше уяснить себе, как это делается, представим себе следующий эксперимент. Пусть
- 4. Указание 1. Обозревайте на ленте ячейку (единственную), под которой подписана буква. Указание 2. Отыщите в таблице
- 5. Но оказывается, что вместо человека, действующего в соответствии с алгоритмом, можно поставить некоторую тьюрингову машину; это
- 6. Непосредственная подача функциональной схемы подражаемой машины и соответствующей конфигурации на ленту универсальной машины в качестве исходной
- 7. Универсальная машина Мы должны в первую очередь позаботиться о выработке надлежащего способа задания функциональных схем и
- 8. Вместо того чтобы изобразить схему в виде двумерной таблицы, насчитывающей k строк и m столбцов, распишем
- 9. Т.о. вместо этой схемы возникает одномерная строка символов /\ q1 /\ Пq4 /\ q2 /\ Лq3
- 10. Для характеристики функциональной схемы и конфигураций вовсе не существенны специфические начертания букв внешнего алфавита и алфавита
- 11. чтобы строку Ω' можно было бы однозначным образом разбить на отдельные кодовые группы; чтобы можно было
- 13. При такой системе кодирования в нашем случае Ω' выглядит так: 100001100000110000110001100000000000110000110000000110000110110000000001… /\ q1 /\ П q4
- 14. Указание 1. Обозревайте в шифре конфигурации кодовую группу (единственную), расположенную непосредственно левее кодовой группы с нечетным
- 15. Указание 7. Если в обозреваемой тройке кодовых групп из шифра схемы второй является группа 10001, то
- 16. Пример: рассмотрим сложение двух чисел. На ленту машины подается два числа (2 и 1), разделенных знаком
- 17. Рассмотрим начальную конфигурацию УМТ (здесь подразумевается, что каждый символ находится в одной ячейке ленты, многоточие означает,
- 18. После выполнения указаний 5-8 получим конфигурацию вида: 1000011000001100000011000110000000001100001100000001 100001101100000001100001100000000011000011000110000000001…/ 10000001100001100000000011000000001100001 Переходим к указанию 1 и т.д.
- 19. В конечном счете, в результате такой детализации алгоритм подражания описывается функциональной схемой машины Тьюринга М, которая
- 21. Скачать презентацию
До сих пор мы придерживались той точки зрения, что различные алгоритмы
До сих пор мы придерживались той точки зрения, что различные алгоритмы
Однако можно построить универсальную тьюрингову машину, способную в известном смысле выполнять любой алгоритм, а значит, способную выполнить работу любой тьюринговой машины.
Алгоритм подражания
Для того чтобы лучше уяснить себе, как это делается,
Алгоритм подражания
Для того чтобы лучше уяснить себе, как это делается,
Пусть на ленту машины подана начальная информация U, и предположим, что некоторому человеку предложено указать, как будет перерабатывать машина эту информацию и во что она переработает ее окончательно. Если этот человек знаком с принципами работы тьюринговых машин, то достаточно ему сообщить, кроме этой начальной информации U, еще функциональную схему машины. Тогда человек, подражая работе машины и выписывая нужные конфигурации, сможет получить тот же результат, что и машина. Но это как раз и означает, что такой человек способен выполнять работу любой тьюринговой машины, если ему только задана ее функциональная схема. Сам же процесс подражания машине в соответствии с ее функциональной схемой может быть регламентирован в виде точного предписания, которое можно сообщить человеку, не имеющему ни малейшего понятия о машинах Тьюринга. Если человека, располагающего таким предписанием, которое естественно называть алгоритмом подражания, снабдить функциональной схемой какой-либо машины Тьюринга и, кроме того, некоторой начальной конфигурацией, изображенной на ленте, то он окажется способным в точности подражать работе соответствующей машины и в результате выдаст тот же результат. Подобный алгоритм подражания можно было бы задать хотя бы в виде следующей системы указаний:
Указание 1. Обозревайте на ленте ячейку (единственную), под которой подписана буква.
Указание
Указание 1. Обозревайте на ленте ячейку (единственную), под которой подписана буква.
Указание
Указание 3. В найденном столбце обозревайте ту тройку букв, которая расположена на пересечении со строкой, обозначенной такой же буквой, какая вписана в обозреваемой ячейке.
Указание 4. Замените букву из обозреваемой ячейки первой буквой из обозреваемой тройки.
Указание 5. Если в обозреваемой тройке второй буквой является !, то остановитесь: процесс окончен.
Указание 6. Если в обозреваемой тройке второй буквой является Н, то замените букву, подписанную под обозреваемой ячейкой, третьей буквой из обозреваемой тройки.
Указание 7. Если в обозреваемой тройке второй буквой является Л, то сотрите букву, подписанную под обозреваемой ячейкой, и левее её запишите третью букву из обозреваемой тройки.
Указание 8. Если в обозреваемой тройке второй буквой является П, то сотрите букву, подписанную под обозреваемой ячейкой, и правее её запишите третью букву из обозреваемой тройки.
Указание 9. Переходите к указанию 1.
Но оказывается, что вместо человека, действующего в соответствии с алгоритмом,
Но оказывается, что вместо человека, действующего в соответствии с алгоритмом,
Заметим в начале, что в описанном нами алгоритме подражания в качестве исходных данных (исходной информации) фигурируют функциональная схема подражаемой машины и соответствующая начальная конфигурация. Эта исходная информация перерабатывается алгоритмом в окончательную конфигурацию, изображающую результат, выдаваемый подражаемой машиной. Универсальная машина должна делать то же самое. Однако здесь приходится учитывать следующие два обстоятельства:
Непосредственная подача функциональной схемы подражаемой машины и соответствующей конфигурации на ленту
Непосредственная подача функциональной схемы подражаемой машины и соответствующей конфигурации на ленту
Универсальная машина (как и всякая тьюрингова машина) может располагать лишь фиксированным конечным внешним алфавитом. Между тем она должна быть приспособлена к приему в качестве исходной информации всех возможных схем и конфигураций, в которых могут встречаться буквы из разнообразных алфавитов со сколь угодно большим числом различных букв.
Универсальная машина
Мы должны в первую очередь позаботиться о выработке надлежащего
Универсальная машина
Мы должны в первую очередь позаботиться о выработке надлежащего
К описанию такого способа мы сейчас и переходим:
Вместо того чтобы изобразить схему в виде двумерной таблицы, насчитывающей k
Вместо того чтобы изобразить схему в виде двумерной таблицы, насчитывающей k
Рассмотрим, например, функциональную схему алгоритма Евклида (таблица 1):
Т.о. вместо этой схемы возникает одномерная строка символов
/\ q1 /\
Т.о. вместо этой схемы возникает одномерная строка символов
/\ q1 /\
Очевидно, по этой строке можно при желании однозначным образом восстановить первоначальную таблицу. Поступая аналогично, можно при рассмотрении конфигураций условиться о том, чтобы букву состояний писать не под обозреваемой буквой, а непосредственно правее её. Рассмотрим пример конфигурации:
q4
Т.о. эта конфигурация перейдет в строку:
| | | | | q4 |
Очевидно, по такому одномерному изображению конфигурации можно при желании однозначным образом восстановить её первоначальный вид.
Для характеристики функциональной схемы и конфигураций вовсе не существенны специфические начертания
Для характеристики функциональной схемы и конфигураций вовсе не существенны специфические начертания
Конечно, можно было выбрать другие буквы, отличные от Л, П, Н и для обозначения сдвигов (влево, вправо, отсутствие сдвига), однако при этом должно быть четко оговорено, какой именно буквой такой сдвиг обозначается. Здесь сказывается тот факт, что каждая из трех букв обозначает вполне определенное действие, которое не заменимо другим.
Учитывая эти обстоятельства, заменим в строке Ω каждую отдельную букву некоторой последовательностью из единиц и нулей (кодовой группой) так, чтобы различные буквы заменялись различными кодовыми группами, но одна и та же буква заменялась бы всюду, где бы она ни встречалась, одной и той же кодовой группой. В результате такой замены, например, строка Ω перейдет в некоторую строку Ω'. Для того чтобы по Ω' можно было восстановить Ω, способ кодирования (отнесения кодовых групп буквам) должен удовлетворять следующим условиям:
чтобы строку Ω' можно было бы однозначным образом разбить на отдельные
чтобы строку Ω' можно было бы однозначным образом разбить на отдельные
чтобы можно было распознавать, какие кодовые группы отнесены каждой из букв Л, П, Н в отдельности, и чтобы можно было различить кодовые группы, отнесенные буквам состояний от тех, которые отнесены буквам внешнего алфавита.
Эти два условия будут наверняка соблюдены при следующем способе кодирования:
В качестве кодовых групп берутся 3+k+m различных слов вида 100…01 (между единицами – сплошь нули).
Тогда разбиение строки Ω' на кодовые группы производится однозначным образом и легко, путем выделения последовательностей нулей, заключенных между двумя единицами.
Сопоставление кодовых групп исходным буквам осуществляется согласно следующей таблице кодирования:
При такой системе кодирования в нашем случае Ω' выглядит так:
100001100000110000110001100000000000110000110000000110000110110000000001…
При такой системе кодирования в нашем случае Ω' выглядит так:
100001100000110000110001100000000000110000110000000110000110110000000001…
/\ q1 /\ П q4 /\ q2 /\ Л q3
Подобную строчку из единиц и нулей, составленную для функциональной схемы или для конфигурации, будем называть шифром функциональной схемы или шифром конфигурации соответственно. По заданному шифру сама схема или конфигурация в своем первоначальном виде легко восстанавливается; поэтому задание схемы или конфигурации можно всегда осуществить посредством их шифров. Разумеется, вместо единицы и нулей можно было бы брать любые другие два знака, например a,b.
Теперь уже нетрудно сообразить, как изменить формулировки указаний 1-9 из первоначального описания алгоритма подражания для того, чтобы получить алгоритм, который перерабатывает шифр схемы подражаемой машины и шифр начальной конфигурации в шифр результирующей конфигурации.
Указание 1. Обозревайте в шифре конфигурации кодовую группу (единственную), расположенную непосредственно
Указание 1. Обозревайте в шифре конфигурации кодовую группу (единственную), расположенную непосредственно
Указание 2 и 3. Отыщите в шифре схемы пару соседних кодовых групп, одинаковую с парой кодовых групп в шифре конфигурации, в которой первая группа является обозреваемой.
Указание 4. Замените в шифре конфигурации обозреваемую кодовую группу на первую кодовую группу из тройки кодовых групп в шифре схемы, стоящей после пары соседних кодовых групп из указаний 2 и 3.
Указание 5. Если в обозреваемой тройке кодовых групп в шифре схемы второй является группа, которая обозначает знак остановки !, например 1000001, то УМТ останавливается и полученный шифр конфигурации будет результатом работы УМТ.
Указание 6. Если в обозреваемой тройке кодовых групп из шифра схемы второй является группа 1001, то в шифре конфигурации замените кодовую группу с нечетным числом нулей третьей кодовой группой из этой обозреваемой тройки.
Указание 7. Если в обозреваемой тройке кодовых групп из шифра схемы
Указание 7. Если в обозреваемой тройке кодовых групп из шифра схемы
Указание 8. Если в обозреваемой тройке кодовых групп из шифра схемы второй является группа 101, то в шифре конфигурации замените кодовую группу с нечетным числом нулей на слева стоящую от неё группу с четным числом нулей, а вместо этой группы с четным числом нулей запишите третью кодовую группу из обозреваемой тройки в шифре схемы.
Указание 9. Переходите к указанию 1.
Дальнейшее рассмотрение этого алгоритма позволяет сводить каждую операцию над кодовыми группами к цепи стандартных операций, осуществимых в тьюринговой машине (замена одного знака другим, сдвиг на один шаг и т.п.). При этом, кроме знаков 1 и 0, из которых построены шифры, будут участвовать и другие буквы, например буква, отделяющая один шифр от другого, буквы, играющие роль временных пометок при просмотре единиц и нулей и другие.
Пример: рассмотрим сложение двух чисел. На ленту машины подается два числа
Пример: рассмотрим сложение двух чисел. На ленту машины подается два числа
Функциональная схема имеет вид:
Кодирование внешнего алфавита и алфавита состояний в данном случае будет выглядеть следующим образом:
Рассмотрим начальную конфигурацию УМТ (здесь подразумевается, что каждый символ находится в
Рассмотрим начальную конфигурацию УМТ (здесь подразумевается, что каждый символ находится в
1000011000001100000011000110000000001100001100000001
100001101100000001100001100000000011000011000110000000001…/
10000110000011000011000000001100001
Далее после выполнения указаний 1-4 получим конфигурацию:
1000011000001100000011000110000000001100001100000001
100001101100000001100001100000000011000011000110000000001…/
1000000110000011000011000000001100001
После выполнения указаний 5-8 получим конфигурацию вида:
1000011000001100000011000110000000001100001100000001
100001101100000001100001100000000011000011000110000000001…/
10000001100001100000000011000000001100001
Переходим к указанию 1 и
После выполнения указаний 5-8 получим конфигурацию вида:
1000011000001100000011000110000000001100001100000001
100001101100000001100001100000000011000011000110000000001…/
10000001100001100000000011000000001100001
Переходим к указанию 1 и
1000011000001100000011000110000000001100001100000001
100001101100000001100001100000000011000011000110000000001…/
1000000110000001100000011000000000001100001100001100001
В конечном счете, в результате такой детализации алгоритм подражания описывается функциональной
В конечном счете, в результате такой детализации алгоритм подражания описывается функциональной
Тем самым установлена теорема:
Теорема. Существуют универсальные машины Тьюринга.