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

Нумерация МТ

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

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

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

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

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

.

Упорядочим команды МТ в соответствии с лексикографическим порядком левых частей команд 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

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

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

Не нашли, что искали? Воспользуйтесь поиском: