Ван Б-машина - Wang B-machine

Эта статья включает Список ссылок, связанное чтение или внешняя ссылка, но его источники остаются неясными, потому что в нем отсутствует встроенные цитаты. Пожалуйста, помогите улучшать эта статья введение более точные цитаты. (Август 2019 г.) (Узнайте, как и когда удалить этот шаблон сообщения)

Как представлено Хао Ван (1954, 1957), его базовая машина B представляет собой чрезвычайно простую вычислительную модель, эквивалентную модели Машина Тьюринга. Это «первая формулировка теории машины Тьюринга в терминах компьютерных моделей» (Minsky, 1967: 200). Имея всего 4 последовательных инструкции, он очень похож, но даже проще, чем 7 последовательных инструкций Машина Пост-Тьюринга. В той же статье Ван представил множество эквивалентных машин, в том числе то, что он назвал W-машина, который представляет собой B-машину с инструкцией «стирания», добавленной к набору инструкций.

Описание

Согласно определению Ванга (1954), B-машина имеет в своем распоряжении только 4 инструкции:

• (1) → : Переместите сканирующую ленту головку на один квадрат ленты вправо (или переместите ленту на один квадрат влево), затем перейдите к следующей инструкции в числовой последовательности;
• (2) ← : Переместите сканирующую ленту головку на один квадрат ленты влево (или переместите ленту на один квадрат вправо), затем перейдите к следующей инструкции в числовой последовательности;
• (3) * : На отсканированной ленте - квадратная метка *, затем перейти к следующей инструкции в числовой последовательности;
• (4) Cn: Условный "переход" (переход, переход) к инструкции "n": Если отсканированный квадрат ленты отмечен, то перейти к инструкции "n" иначе (если отсканированный квадрат пустой) перейти к следующей инструкции в числовой последовательности.

Его пример представляет собой простую инструкцию B-машины (стр. 65):

1. *, 2. →, 3. C2, 4. →, 5. ←

Он переписывает это как набор упорядоченных пар:

{(1, *), (2, →), (3, C2), (4, →), (5, ←)}

W-машина Вана - это просто B-машина с одной дополнительной инструкцией.

• (5) E : В сканируемой ленте-квадрате сотрите отметку * (если она есть), затем перейдите к следующей инструкции в числовой последовательности.

Смотрите также

• Клеточный автомат Кодда

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

• Хао Ван (1957), Вариант теории вычислительных машин Тьюринга, JACM (Журнал Ассоциации вычислительной техники) 4; 63-92. Представлено на собрании Ассоциации 23-25 ​​июня 1954 г.
• З. А. Мельзак (1961) получено 15 мая 1961 г. Неформальный арифметический подход к вычислимости и вычислениям, Канадский математический бюллетень, т. 4, вып. 3. Сентябрь 1961 г., стр. 279–293. Мелзак не дает никаких ссылок, но признает «пользу разговоров с доктором. Р. Хэмминг, Д. Макилрой и В. Высоцкий из телефонных лабораторий Bell и с доктором Х. Ван из Оксфордского университета ".
• Иоахим Ламбек (1961) получен 15 июня 1961 г. Как программировать бесконечные счеты, Математический вестник, т. 4, вып. 3. Сентябрь 1961 г., стр. 295–302. В своем Приложении II Ламбек предлагает «формальное определение« программы »». Он ссылается на Мелзака (1961) и Клини (1952). Введение в метаматематику.
• Марвин Мински (1967), Вычисления: конечные и бесконечные машины, Prentice-Hall, Inc., Энглвуд Клиффс, Нью-Джерси.В частности, см. Стр. 262ff (курсив в оригинале):

«Теперь мы можем продемонстрировать замечательный факт, впервые показанный Ван [1957], что для любой машины Тьюринга Т есть эквивалентная машина Тьюринга Т_N который никогда не меняет однажды написанный символ! Фактически мы построим двухсимвольную машину Т_N который может только заменить пустые квадраты на своей ленте на единицы, но не может заменить 1 на пустое поле ». Затем Мински предлагает доказательство этого.