Диаграмма Тьюринга

Диаграмма Тьюринга — графический способ описания работы машины Тьюринга. Состоит из символов, обозначающих данные машины Тьюринга, имеющие общий рабочий алфавит, символа «точка», обозначающего место, где нужно начинать работу, стрелок с написанными на них буквами. В диаграмме Тьюринга символ «точка» встречается только один раз, из любого символа выходит не более одной стрелки с каждой буквой алфавита. Каждой таблице Тьюринга $T$ над алфавитом $A_{t}$ можно эффективным образом сопоставить диаграмму $D$, образованную символами $r,l,a_{0},...,a_{t}$ и точкой, так, чтобы определяемая этой диаграммой машина Тьюринга моделировала машину Тьюринга с таблицей $T$.

См. также

• Машина Тьюринга

Литература

• Эббинхауз Г.Д., Якобс К., Ман Ф.К., Хермес Г. Машины Тьюринга и рекурсивные функции. — М.: Мир, 1972. — 262 с.