April 28th, 2021

Тьюринг-полнота компьютера с одной операцией.

Тьюринг-полнота компьютера с одной операцией.
--
https://neerc.ifmo.ru/wiki/index.php?title=Тьюринг-полнота
Тьюринг-полнота
--

Собственно это не неожиданность. Это нормально.
В частности НАМ=нормальные алгоритмы Маркова суть машина с одной операцией - подстановка.
https://ru.wikipedia.org/wiki/Нормальный_алгоритм
http://mathhelpplanet.com/static.php?p=normalnyye-algoritmy-markova

one instruction set computer
—-
https://en.wikipedia.org/wiki/One-instruction_set_computer
Компьютер с одним набором инструкций ( OISC ), иногда называемый конечным компьютером с сокращенным набором инструкций ( URISC ), представляет собой абстрактную машину, которая использует только одну инструкцию, что устраняет необходимость в коде операции на машинном языке . [1] [2] [3] При разумном выборе одной инструкции и учитывая бесконечные ресурсы, OISC может быть универсальным компьютером так же, как традиционные компьютеры, которые имеют несколько инструкций. [2] : 55 OISC рекомендованы в качестве вспомогательных средств в обучении компьютерной архитектуре [1]: 327 [2] : 2 и использовались в качестве вычислительных моделей в исследованиях структурных вычислений. [3]
--
Обычный выбор для отдельной инструкции:
Вычесть и перейти, если меньше или равно нулю
Вычесть и перейти, если отрицательное
Вычесть, если положительный результат else
Обратное вычитание и пропуск при заимствовании
Перемещение (используется как часть архитектуры, запускаемой транспортом)
Вычесть и перейти, если не ноль (SBNZ a, b, c, пункт назначения)
Cryptoleq (гетерогенные зашифрованные и незашифрованные вычисления)
--

***В реальном мире существует странный микропроцессор MAXQ2000.
У него тоже всё через пересылки в разные регистры реализовано. Мнемоники они, конечно, назначили привычные, но под ними только move.
----
Однокомандный dzen-процессор ;)
https://wasm.in/threads/odnokomandnyj-dzen-processor.1283/
Число регистров - 2^k (k должно быть не менее 3, наверное :)
(к ним также относится счётчик команд ip)
Архитектура - трехадресная
Число команд - одна единственная (условное вычитание)
Число флагов - один (f - флаг переполнения)

Основной цикл:
Проверить флаг
если f=0
1) считать команду из памяти
2) если тип команды 01 или 10 - считать операнд из памяти
3) вычислить разность и установить флаг при переполнении
4) записать результат в приёмник и увеличить счетчик команд
если он(ip) не является приёмником данной команды
иначе
сбросить флаг
перейти к началу
---

Неожиданная полнота по Тьюрингу повсюду
https://habr.com/ru/post/429602/
---

(no subject)

А.А.Марков (1947) и советская школа конструктивизма развили вариант математики, последовательно проводящий идею о том, что нет ничего, кроме конструктивных объектов, а алгоритмы отождествляются с их программами. Он ввел «принцип Маркова», явно разделивший обоснования и построения, разница между которыми с самого начала ощущалась в интуиционизме. Содержательно принцип Маркова гласит, что для обоснования уже проделанных построений можно пользоваться классической логикой (это показал Н.А.Шанин, построив алгоритм конструктивной расшифровки, разбивающий любую формулу на явное построение и классическое обоснование данного построения). Польская школа пошла по другому пути, ограничиваясь конструктивными объектами, но сохраняя классическую логику.

Реализуемость выявила, что интуиционистские теории могут расходиться с классическими. Напр., если А(х) – неразрешимое свойство натуральных чисел, то конструктивно верна формула – ∀х(А(х) Ѵ⌉А(х)).

Зафиксировав понятие вычислимой последовательности, мы сохраняем свободу при определении операторов высших типов. Первым это показал Клини, построив общерекурсивную реализуемость, при которой выполнена схема
https://iphlib.ru/library/collection/newphilenc/document/HASH915ab65b4715ec43784291
Н.Н.Непейвода
http://www.mathnet.ru/rus/person28672