Меню сайта |
|
|
Наш опрос |
|
|
Статистика |
Онлайн всего: 1 Гостей: 1 Пользователей: 0 |
|
Форма входа |
|
|
|
Главная » 2014 » Декабрь » 26 » SUBLEQ языки по Тьюрингу
23:43 SUBLEQ языки по Тьюрингу |
|
|
хех :) кстати, я тут вспомнил про свои забавы на старших курсах
|
|
|
Любой язык программирования полон по Тьюрингу, если в нём есть математика, условия и goto
|
|
|
один из самых минималистических языков программирования называется SUBLEQ.
|
|
|
в этом языке всего одна команда - SUBLEQ, которая на вход принимает три числа. Ячейку 1, ячейку 2 и ячейку 3.
В общем случае операция Subleq вычитает из ячейки 1 ячейку 2, записывает результат в ячейку 1, и если результат меньше либо равен 0, переходит к следующей операции SUBLEQ, считывая новые ячейку 1, 2 и 3 начиная с адреса из ячейки 3. Иначе как ячейки 1,2,3 берутся следующие ячейки
|
|
|
Кажущаяся простота этого языка называется "Тьюрингова трясина". Совсем непросто для такого языка придумать операции сложения, сравнения произвольных чисел, циклы и так далее
|
|
|
Но как только у тебя есть "кирпичики" для всех этих операций - ты легко можешь написать компилятор простого языка в SUBLEQ :)
|
|
|
Конечно, простейшая программа на SUBLEQ превращается в огромного запутанного монстра, и вычисляется очень долго. Но зато можно построить рабочий процессор SUBLEQ из трех десятков логических микросхем
|
|
|
Любопытный факт состоит в том, что помимо SUBLEQ, есть ещё очень интересный язык программирования - который на первый взгляд выглядит совершенно абсурдным, но он тоже полон по тюьрингу
|
|
|
язык называется BBJ, или BitBitJump
|
|
|
|
Предположим, разрядность процессора, умеющего выполнять только команду BBJ, составляет 32 бита. Тогда этот компьютер делает следующее:
0) при включении записывает в регистр PC число 0, в регистры A1 и A2 тоже число 0
1) считывает 32 бита в регистр A1 начиная с 1-битовой ячейки с адресом PC
2) считывает 32 бита в регистр A2 начиная с 1-битовой ячейки с адресом PC+32
3) считывает 1 бит из памяти по адресу A1 в регистр M
4) записывает 1 бит из регистра M по адресу A2
5) считывает 32 бита в регистр PC начиная 1-битовой ячейки с адресом PC+64
6) переходит к шагу 1
|
|
|
Всё, что делает этот компьютер - считывает X бит - как адрес A1, потом считывает ещё X бит как адрес A2, потом копирует один бит из A1 в A2, потом считывает ещё X бит, и воспринимает их как адрес новой команды BBJ
|
|
|
звучит безумно, но на таком компьютере можно всё
|
ttt
|
Просмотров: 1216 |
Добавил: i_elf
| Рейтинг: 0.0/0 |
|
Поиск |
|
|
Календарь |
|
|
Архив записей |
|
|
|