Галерея машин Тьюринга

Следующая статья является дополнением к статье Машина Тьюринга .

Машина Тьюринга как механическое устройство

Показанная здесь машина Тьюринга состоит из специальной бумажной ленты , которую можно как стирать, так и писать с помощью «отметки». Возможно, ТАБЛИЦА сделана из аналогичного устройства чтения бумажной ленты, предназначенного только для чтения, или, возможно, она читает перфокарты . Биограф Тьюринга Эндрю Ходжес (1983) писал, что Тьюринг в детстве любил пишущие машинки . «Чудесная машина» — механический процесс, который мог бы решить проблему решения Гильберта » (Ходжес, стр. 98) была предложена Г.Х. Харди , одним из учителей Тьюринга. Тем не менее, «его машина не имела очевидной модели ни в чем, существовавшем в 1936 году, за исключением общих черт новой электротехнической промышленности с их телетайпами , телевизионным « сканированием » и автоматическими телефонными станциями . Это было его собственное изобретение». (Ходжес, стр. 109)

Дэвис (2000) говорит, что Тьюринг построил двоичный умножитель из электромеханических реле (стр. 170). Как отмечалось в разделе истории алгоритмов, перфолента или печатная бумажная лента и перфокарты были обычным явлением в 1930-х годах.

Булос и Джеффри (1974, 1999) отмечают, что «нахождение в том или ином состоянии может означать, что та или иная шестерня определенной шестерни находится вверху…» (стр. 21).

Машина Тьюринга как «бедная рожа» внутри коробки, тянущая коробку по рельсу

«Нас не интересуют механика или электроника этого вопроса. Возможно, самый простой способ представить эту вещь довольно грубо: внутри коробки находится человек, который все читает, пишет, стирает и перемещает. (Коробка) дна нет: бедная морда просто ходит между завязками, таща за собой коробку.) У человека есть список из m инструкций, записанных на листе бумаги. Он находится в состоянии ци, когда выполняет инструкцию номер i. [и т. д.]» (Булос и Джеффри (1974, 1999), стр. 21)

Это описание близко соответствует «формулировке I» Эмиля Поста для «конечного комбинаторного процесса»: человек, оснащенный «фиксированным неизменным набором инструкций» и следующий ему, движется влево или вправо через «бесконечную последовательность пространств или блоков». и, находясь в коробке, либо печатайте на листе бумаги одиночный «вертикальный штрих», либо стирайте его (Пост 1936 года, перепечатано в Undecidable , стр. 289). Формулировка Поста была первой опубликованной в своем роде; он опередил Тьюринга на несколько месяцев.

Оба описания — Поста, Булоса и Джеффри — используют более простые четырехкортежности, а не пятикортежи для определения «m-конфигураций» (инструкций) своих процессов.

Робот выполняет инструкции

Эту модель предложил Стоун (1972):

«Давайте примем точку зрения, что компьютер — это робот, который выполнит любую задачу, которую можно описать как последовательность инструкций» (с. 3).

Стоун использует робота для разработки своего понятия алгоритма . Это, в свою очередь, приводит его к описанию машины Тьюринга и его утверждению:

«Факты, похоже, указывают на то, что каждый алгоритм для любого вычислительного устройства имеет эквивалентный алгоритм машины Тьюринга… если [тезис Чёрча] верен, то, безусловно, примечательно, что машины Тьюринга с их чрезвычайно примитивными операциями способны выполнять любые вычисления». то, что может выполнять любое другое устройство, независимо от того, насколько сложное устройство мы выбираем». (стр. 13)

Другие изображения

Художественное изображение машины Тьюринга.
Модель машины Тьюринга

Ссылки

Дополнительные сведения см. в основной статье « Машина Тьюринга» .