Нумерация МТ

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

A={a0,..,ai,…} – внешний алфавит МТ (счетное множество).

Q={q0, q1, …, qj,…} – внутренние состояния МТ (счетное множество).

Пусть для всех МТ a0 – пустой символ, q0 – заключительное состояние, q1 – начальное состояние.

Каждому символу из множества {Л, П, С, a0, a1,…, ai,…, q0, q1, …qj… } поставим в соответствие двоичное число:

	Символ	Код	Число нулей в коде
Д	Л
П
С
А	а0
а1
…
ai	10………0	2i+4
….
Q	q0
q1
….
qj	10………0	2j+5
…

Команде МТ поставим в соответствие двоичное число:

.

Упорядочим команды МТ в соответствии с лексикографическим порядком левых частей команд q1a0, q1a1,…q2a0,…. и т. д. Получим последовательность команд I1,…In(m+1), где n – число символов в алфавите А, m – число состояний в множестве Q.

Тогда МТ можно поставить в соответствие двоичное число вида:

Код(Т)=Код(I1)Код(I2) …..Код(In(m+1)).

Пример.

A={a0,a1}

Q={q0,q1}

I1:q1a0→q0a0C

I2:q1a1→q0a1C

Тогда Код(Т)=

Такое кодирование является алгоритмической процедурой. Зная код МТ можно однозначно восстановить множество ее команд. Код МТ можно рассматривать как двоичную запись натурального числа. Такое число называется номером МТ.

Дата добавления: 2014-01-15