Диаграмма Тьюринга (:ngijgbbg M,Zjnuig)
Перейти к навигации
Перейти к поиску
Диаграмма Тьюринга — графический способ описания работы машины Тьюринга. Состоит из символов, обозначающих данные машины Тьюринга, имеющие общий рабочий алфавит, символа «точка», обозначающего место, где нужно начинать работу, стрелок с написанными на них буквами. В диаграмме Тьюринга символ «точка» встречается только один раз, из любого символа выходит не более одной стрелки с каждой буквой алфавита. Каждой таблице Тьюринга над алфавитом можно эффективным образом сопоставить диаграмму , образованную символами и точкой, так, чтобы определяемая этой диаграммой машина Тьюринга моделировала машину Тьюринга с таблицей [1].
Примечания
[править | править код]- ↑ Эббинхауз, 1972, с. 55.
См. также
[править | править код]Литература
[править | править код]- Эббинхауз Г.Д., Якобс К., Ман Ф.К., Хермес Г. Машины Тьюринга и рекурсивные функции. — М.: Мир, 1972. — 262 с.