Тьюринг-полнота компьютера с одной операцией.
Тьюринг-полнота компьютера с одной операцией.
--
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/
---
https://esolangs.org/wiki/OISC
OISC - One Instruction Set Computer (по аналогии с RISC и CISC), машина, предоставляющая только одну инструкцию. Аббревиатура URISC (Ultimate RISC) использовалась в некоторых публикациях с тем же значением, что и OISC.
Список OISC
--
Все машины на одной странице
https://esolangs.org/wiki/Category:Turing_tarpits
--
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/
---
https://esolangs.org/wiki/OISC
OISC - One Instruction Set Computer (по аналогии с RISC и CISC), машина, предоставляющая только одну инструкцию. Аббревиатура URISC (Ultimate RISC) использовалась в некоторых публикациях с тем же значением, что и OISC.
Список OISC
--
Все машины на одной странице
https://esolangs.org/wiki/Category:Turing_tarpits