Два слова называются графически равн
ыми если они имеют одинаковые длины и на с о ответству
ю щих местах в них находятся равные буквы. Операции применяе
мые к словам, есть инс т рукции. Мы говорим, что инструкция пр
имененная к слову 1 переводит слово 1 в слово 2. Слово 1 и слово 2 Ц слова в одн
ом алфавите.
На сегодняшний момент соответств
ием соответствий является соответствие: «р а бочая лен
та машины Тюринга-Поста»:

рабочая лента машины Тюринга-По
ста

ячейка1 содержимое ячейки (сим
вол1)
ячейка2 содержимое ячейки (сим
вол2)
ячейка3 содержимое ячейки (символ3)
ячейка4 содержимое ячейки (символ1)
ячейка5 содержимое ячейки (символ3)
ячейка6 содержимое ячейки (символ2)
и т.д.

Рабочая лента бесконечна. О символы, которые могут записываться как соде
рж а ние ячейки говорят, что они заданы на определенном а
лфавите.
М ашин а Тюринга-П
оста -- механическое устройство состоящее из следующих о
с новных ча с тей.
1) В машине имеется потенциально неограниченная память, разбитая на о
т дельные линейно-упорядоченные ячейки. В каждой ячейке мож
ет быть записан символ из некот о рого конечного алфавита, и
ли она может быть пустой. Считают, что в ячейке записан ос о б
ый символ, называемый пустым. В каждый момент времени память, обычно назы
ваемая рабочей лентой машины, состоит из конечного числа ячеек, однако п
ри необходим о сти к ней могут быть пристроены слева или спр
ава новые ячейки с зап и санных в них пустым символом. Рабоча
я лента и информация, записанная в ней, представляются конечной ц е
почкой символов над словарем раб о чей
ленты.
2) Помимо рабочей ленты в машине Тюринга имеется еще и другое запом
инающее устройство. Это регистр состояний Ц особая память, рассчитанна
я на хранение одного символа. Символ, который запоминается в регистре, вы
бирается из конечного множества, определяющего множество состояний ма
шины.
3) В каждый момент времени машина Тюринга анализирует не всю инфор
мацию, хранящуюся на рабочей ленте, а содержимое лишь одной ячейки этой л
енты. Для опред е ления этой ячейки служит управляющая голо
вка, которая всегда указывает на некоторую ячейку рабочей ленты.

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

2) Машина изменяет состояние и продвигает управляющую головку на о
дну ячейку влево.
3) Машина изменяет состояние и продвигает управляющую головку на о
дну ячейку вправо.
В последних двух случаях может оказаться, что до такта управляюща
я головка ук а зывала на самую левую или самую правую ячейку
рабочей ленты. Если требуется прои з вести сдвиг влево (или, с
оответственно, вправо), то к рабочей ленте пристраивается новая ячейка с
записанным в ней пустым символом.
Машина Тюринга может использоваться для вычисления инструкций, аргуме
нты и значения которых представляются цепочками символов конечных алф
авитов. При этом машина начинает работу в так называемой начальной ситуа
ции, которая характеризуется следующим образом:
1 ) на рабочей ленте записан аргумент вычисляемой инстр
укции;
2 ) управляющая головка указывает на ячейку, в кот
орой записан самый левый си м вол аргумента;
3 ) машина находится в некотором заранее выбранн
ом состоянии, которое назыв а ется начальным.
Начиная работу в начальной ситуации, машина работает до тех пор, п
ока не ок а жется в некотором особом состоянии, называемом з
аключительным. Значением вычи с ляемой инструкции считает
ся цепочка непустых символов, выписанных слева направо из р а
бочей ленты после окончания работы машины.

47 . И гра на
рулетке при ставке 10 рублей на цифру с выигрышем на трет ь
ей ставке и десятью ставками будет отражено на рабочей ленте маш
ины Тюринга-Поста следу ю щим обр а зом:

Исходное состояние ленты: 10 10 10 10 10 10 10 10 10 10
Результат: 0 0 350 0 0 0 0 0 0 0
Данное соответствие не является функциональным, т.к 10 рублям соо
тветствуют как 0 так и 350, однако это соответствие имеет решение согласно а
бстракции машины Т ю ринга-Поста.

48 . Де
ятельность алгоритма Ц предмет для осмысления физиологами, ибо эта де
я тельность может рассматриваться как модель физиологи
ческого представления об асс о циации. Ассоциация Ц то,
как могут объяснить физиологи связь аргумента и значения и н
струкции. Математическая модель однако более выразительна. В эт
ой модели два пре д ставления Ц значение и аргумент, не п
росто связаны в сознании Ц ассоциированы Ц а пр о исхо
дит преобразование одного представления в другое. Представление психо
логов и ф и зиологов об ассоциации не заходит столь дале
ко. При этом это преобразование характер и зуется нал
и чием третьих, четвертых, n -пре
дставлений, связанных с первыми двумя. Это преобразование производится
в оперативной памяти, которая по шагам (тактам) произв о д
ит следующее изменение: аргумент Ц представление1, -- …, -- представление
N Ц знач е ние. Так, чтобы преобр
азовать число 3 в число 4 имеется аргумент, который двоично в ы
глядит как 011 и значение, которое двоично выглядит как 100. Но кроме э
тих представл е ний, имеются еще вспомогательные предст
авления 010, 000 на первом и втором шаге р а боты алгоритма, ког
да соответственно стираются единицы в соответствующих разрядах.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62