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

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

См. такжеПравить

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

ЛитератураПравить

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