Проблема самоприменимости. Нумерация МТ

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

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

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

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

Символ

Код

Число  нулей в коде

Д

Л

10

1

П

100

2

С

1000

3

А

а0

10000

4

а1

1000000

6

ai

10………0

2i+4

….

Q

q0

100000

5

q1

10000000

7

….

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

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

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

 

Логика - доступно для всех