Ван Б-машина

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

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

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

Его примером является простая команда 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 г. Неформальный арифметический подход к вычислимости и вычислениям, Canadian Mathematical Bulletin, vol. 4, вып. 3. Сентябрь 1961 г., стр. 279–293. Мелзак не дает никаких ссылок, но признает «пользу разговоров с докторами Р. Хэммингом, Д. Макилроем и В. Высоцким из телефонных лабораторий Bell и с Доктор Х. Ван из Оксфордского университета ".
• Иоахим Ламбек (1961) получил 15 июня 1961 г. Как программировать бесконечные счеты, Математический бюллетень, т. 4, вып. 3. Сентябрь 1961 г., стр. 295–302. В своем Приложении II Ламбек предлагает «формальное определение« программы »». Он ссылается на Мелзака (1961) и Клини (1952) Введение в метаматематику.
• Марвин Мински (1967), Вычисления: конечные и бесконечные машины, Prentice-Hall, Inc., Энглвуд Клиффс, штат Нью-Джерси. 262ff (курсив в оригинале):

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