МАТЕМАТИЧЕСКИЕ ОСНОВЫ ИНФОРМАТИКИ
Четверг, 17.01.2019, 16:53
ГлавнаяРегистрацияВход Приветствую Вас Гость | RSS

Меню сайта

Наш опрос
Какой язык программирования Вы изучаете
Всего ответов: 954

Статистика

Онлайн всего: 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

Просмотров: 503 | Добавил: i_elf | Рейтинг: 0.0/0
Всего комментариев: 0
Поиск

Календарь
«  Декабрь 2014  »
ПнВтСрЧтПтСбВс
1234567
891011121314
15161718192021
22232425262728
293031

Архив записей

Друзья сайта
  • Творческий учитель
  • Сайт ООАКМР
  • Школьный сайт
  • Информатика учебник
  • МОИ

  • Copyright MyCorp © 2019 Сделать бесплатный сайт с uCoz