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

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

См. также

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

Литература

• Шаблон:Книга