Ван Б-машина

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

Описание

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

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

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