Ван Б-машина - 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 на пустое поле ». Затем Мински предлагает доказательство этого.