Следующая статья является дополнением к статье Машина Тьюринга .
Машина Тьюринга как механическое устройство
Показанная здесь машина Тьюринга состоит из специальной бумажной ленты, которую можно стирать, а также писать с помощью «метки». Возможно, ТАБЛИЦА сделана из аналогичного устройства чтения бумажных лент, предназначенного только для чтения, или, возможно, он считывает перфокарты . Биограф Тьюринга Эндрю Ходжес (1983) написал, что Тьюринг в детстве любил пишущие машинки . «Чудесная машина» - механический процесс, который мог бы работать над проблемой решения Гильберта »(Ходжес, стр. 98) был предложен Дж. Х. Харди , одним из учителей Тьюринга. Тем не менее, «его машина не имела очевидной модели ни в чем, существовавшем в 1936 году, за исключением в общих чертах новой электротехнической промышленности с их телетайпами , телевизионным « сканированием »и подключениями к АТС . Это было его собственное изобретение». (Ходжес стр.109)
Дэвис (2000) говорит, что Тьюринг построил двоичный умножитель из электромеханических реле (стр. 170). Как отмечалось в разделе истории алгоритмов, перфоленты или печатные бумажные ленты и перфокарты были обычным явлением в 1930-х годах.
Булос и Джеффри (1974, 1999) отмечают, что «пребывание в том или ином состоянии может означать наличие того или иного зубца определенной передачи наверху ...» (стр. 21).
Машина Тьюринга как «бедная кружка» внутри коробки, тянущая коробку по рельсам
- «Нас не интересуют механика или электроника этого вопроса. Возможно, самый простой способ представить это довольно грубо: внутри коробки находится человек, который все читает, пишет, стирает и перемещает» (коробка у него нет дна: бедная кружка просто ходит между галстуками, таща за собой коробку.) У мужчины есть список из m инструкций, записанных на листе бумаги. Он находится в состоянии ци, когда выполняет инструкцию номер i. [и т. д.] »(Булос и Джеффри (1974, 1999), стр.21)
Это описание близко следует «Формулировке I» Эмиля Поста для «конечного комбинаторного процесса»: человек, оснащенный «фиксированным неизменным набором инструкций» и выполняющий его, движется влево или вправо через «бесконечную последовательность пространств или ящиков» и находясь в коробке, он либо печатает на листе бумаги один «вертикальный штрих», либо стирает его («Пост 1936» перепечатан в Undecidable, стр. 289). Формулировка Поста была первой опубликованной в своем роде; он опередил Тьюринга на несколько месяцев.
Оба описания - Post, Boolos и Jeffrey - используют более простые 4-кортежи, а не 5-кортежи для определения «m-конфигураций» (инструкций) своих процессов.
Робот выполняет инструкции
Эта модель была предложена Стоуном (1972):
- «Примем точку зрения, что компьютер - это робот, который будет выполнять любую задачу, которую можно описать как последовательность инструкций» (стр. 3).
Стоун использует робота, чтобы развить свое представление об алгоритме . Это, в свою очередь, приводит его к описанию машины Тьюринга и его утверждению:
- «Доказательства, кажется, указывают на то, что каждый алгоритм для любого вычислительного устройства имеет эквивалентный алгоритм машины Тьюринга ... если [тезис Черча] верен, то, безусловно, замечательно, что машины Тьюринга с их чрезвычайно примитивными операциями способны выполнять любые вычисления. что любое другое устройство может работать, независимо от того, насколько сложное устройство мы выберем ». (стр.13)
Рекомендации
См. Основную статью о машине Тьюринга .