Галерея машин Тьюринга - Turing machine gallery

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

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

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

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

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

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

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

Плохая кружка в коробке, чтение, письмо, стирание согласно его списку инструкций. После того, как Булос и Джеффри рис. 3-1, с. 21 год

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

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

Оба описания - Post, Boolos и Jeffrey - используют более простые 4-кортежи, а не 5-кортежи для определения «m-конфигураций» (инструкций) своих процессов.

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

Это робот с консолью, которая может работать как двухсимвольный бобер с тремя состояниями. Робот работает с лентой, на которой изначально было напечатано 0 / пробелов. Робот посмотрел на символ в окне (символ 0), прочитал инструкцию («состояние») C и собирается ПЕЧАТЬ 1. Затем он нажмет кнопку «Лента ВЛЕВО». Наконец, он будет смотреть на инструкцию ("состояние") B. (Механизм печати / стирания находится вне поля зрения, под окном. Возможно, лента чистая и механизм снимает липкие 0 и наклеивает 1 для ПЕЧАТИ и наоборот для СТЕРЕТЬ.)

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

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

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

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

Рекомендации

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