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

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