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

По[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. Нумерация алгоритмов, наборов чисел, слов и машин Тьюринга.