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

Примечания

См. также

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

Литература

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