Нумерация слов и словарные функции

По[i262] аналогии с числовыми можно рассмотреть функции над словами — словарные функции. Пусть задан алфавит A={a₁,a₂..., a_p}, где a_i (i=1,2,...,p) — буквы. Несколько букв, записанных рядом (конкатенация) образуют слово в алфавите A. Слово, не содержащее ни одной буквы называется пустым(∅.) Пусть w_i(i=1,2,...) — слова в алфавите A. В качестве простейших (элементарных) функций можно выбрать такие: 1) аналог функции обнуления o(w)= ∅; 2) аналог функции следования s_i(w)=wa_i; 3) аналог функции проектирования где (1≤m≤n;n=1,2,...). По аналогии вводятся операции подстановки, рекурсии и минимизации.

Вместо этого можно ввести алфавитную нумерацию следующим образом. Пустое слово ∅ имеет номер 0. Однобуквенное слово a_i, то есть символ алфавита, имеет номер i для =1,2,...,p. Номер слова по определению то есть слову соответствует натуральное число, записанное в p-ичной системе счисления. Таким образом, все результаты, полученные для числовых функций могут быть перенесены на словарные.

Другими словами, это можно определить так. Пусть дан алфавит А = {a1, a2, …, ar[i263] }, где r – число букв или символов алфавита. Например, для латиницы это - r=26. На множестве букв алфавита согласно правилам соответствующей грамматики можно сформировать множество слов конечной длины A*={α1, α2, …, β1, β2,[i264] …, ε}, где ε -пустое слово. Согласно правилам алгоритма Маркова это могут быть слова αi и βi. [i265] Тогда алфавитная нумерация определяется как: h(ε)=0 и h(a_i1,a_i2,...,a_is [i266])=i_s+i_s-1 [i267] r+i_s-2+r2[i268] +.. i₁[i269] +[i270] r_s-1 [i271]. Поскольку при фиксированном r каждое положительное число n однозначно представимо в виде:

n= i_s+i_s-1 ⋅r+i_s-2⋅r²+.. i₁⋅r^s-1, где 1 ≤ i ≤ r – порядковый номер символа в алфавите А, нижний индекс которого указывает его место в слове αi или βi[i272]. Например, для нормального алгоритма Маркова произведения двух чисел алфавит содержит пять символов Vт={|, ⋅, #, (,)}, а протокол правила α1[i273]:= ⋅| | → β1[i274]:= (⋅|, α2[i275]:= ⋅|# → β2[i276]:= (#, α3[i277]:= |(→ β3[i278]:= (|), α4[i279]:=)(→ β4[i280]:= (), α5[i281]:=)| → β5[i282]:= |), α6[i283]:= (| → β6[i284]:= (, α7[i285]:= () → β7[i286]:=), α8:=) → β8:= |, α9:= |# → β9[i287]:= •|#.

Номера некоторых слов: α1:= ⋅| |: n = 1+1⋅5+2⋅52 = 56, β1:= (⋅|: n = 1+2⋅5+4⋅52 =111, α2:= ⋅|#: n = 3+1⋅5+2⋅52 = 58, β2:= (#: n = 3+4⋅5 = 23, α3:= |(: n = 4+1⋅5 = 9, β3:= (|): n = 5+1⋅5+4⋅52 = 110, α4:=)(: n = 4+5⋅5 = 29.

β4:= (): n = 5+4⋅5 =25 и т.д.

β4:= (): n = 5+4*5 =25 и т.д.

[i288] Следовательно, цифровой код протокола есть (56→111, 58→23, 9→110, 29→25, 26→10, 21→4, 25→5, 5→1, 8→8). Далее нужно найти номер для набора двух чисел команды. Так может быть сформирована упорядоченная последовательность номеров команд, моделирующая заданный алгоритм.

 

 

Нумерация машин Тьюринга

Для успешного использования левой и правой полу-[i289] лент машины Тьюринга была предложена система кодирования символов трех алфавитов.

Таблица 1.

 

Согласно этой системе (таблицуотформатировать надо) символы «сдвига головки» были представлены кодами 101[i290], 102[i291], 103[i292], символы «внешней памяти» - кодами с числом нулей равном (2⋅[i293] i + 4), символы «внутренней памяти» – кодами с числом нулей (2⋅[i294] i + 5).Символ # интерпретируются как пробел между числами или словами.

Тогда любой команде (i) машины Тьюринга, имеющей вид qm[i295] as[i296] →ql[i297] au[i298] D может быть сопоставлен код: код (i)= код(qm[i299])код(as[i300])код(ql[i301])код(an[i302])код(D), в котором коды всех символов приписаны друг к другу без каких-либо пробелов. Разделителем слов или чисел являются 1, так как код любого символа начинается с 1, а их различие определяется количеством нулей в коде. На левой полуленте записывают протокол машины Тьюринга, а на правой – ее текущую конфигурацию. В процессе вычисления заданной функции на правой полуленте определяется левая часть команды qm[i303] as[i304], где qm[i305] текущее состояние управляющего устройства, as[i306] – символ на информационной ленте под считывающей головкой. Затем на левой полуленте находится соответствующая команда qm[i307] as[i308] →ql[i309] au[i310] D. После этого машина Тьюринга записывает в обозреваемую ячейку символ au[i311], переводит управляющее устройство в состояние ql[i312] и перемещает головку не более как на одну ячейку вправо или влево.

Например, для машины Т1 протокол будет записан на левой полу ленте так: код(Т1)=10510610910410110910610910410110910410111041021011104107106103. [i313]

Указанное кодирование является алгоритмической процедурой. Каждые пять групп единиц и нулей представляют одну команду. Следовательно, любой функции, вычисляемой на машине Тьюринга, может быть сопоставлен код (Тi[i314]) и по коду (Тi[i315]) можно выделить алгоритм вычисляемой функции. Так может быть организована нумерация алгоритмов машины Тьюринга.

В 70-е годы XX века была предложена алгоритмическая модель, представляющая собой идеализированную ЭВМ. Эта модель состоит из бесконечного числа регистров R1, R2, R3[i316],...,, в каждом из которых может быть записано натуральное число. Часть этих регистров используют для хранения команд (аналог левой полуленты), остальные - для хранения данных, промежуточных вычислений и окончательных результатов (аналог правой полуленты). Модель позволяет организовать произвольный доступ к ячейкам памяти. Такую модель назвали «машиной произвольного доступа» - МПД.

Набор команд МПД включает:

• команду обнуления: действие команды заключается в замене содержимого регистра Rn[i317] на 0, т.е. Rn[i318]:= 0,

• команду прибавления единицы: действие команды заключается в увеличении содержимого регистра Rn[i319] на 1, т.е. Rn[i320]:= Rn[i321] + 1,

• команду переадресации: действие команды заключается в замене содержимого регистра Rn[i322] числом rm, хранящимся в регистре Rm, т.е. Rn:=Rm,

• команду условного перехода: действие команды заключается в сравнении содержимого регистров Rn и Rm:

- если Rn=Rm, то перейти к исполнению команды qi;

- если Rn≠Rm, то перейти к исполнению команды qj.

[i323] Упорядоченная последовательность команд формирует программу МПД.

 

ЗАКЛЮЧЕНИЕ

В данной контролируемой самостоятельной работе я изучал следующие вопросы:

1. Интуитивное понятие алгоритма.

2. Алгоритмические модели и их основные типа

3. Свойства алгоритма

4. Машина Тьюринга

5. Операции и применения машины Тьюринга.

6. Вычислимость по Тьюрингу и разрешимость.

7. Проблема самоприменимости.

8. Нумерация алгоритмов, наборов чисел, слов и машин Тьюринга.