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