Машина Тюринга

thunder87l

Господа любители паять железяки и извращаться с цифровой логикой, а давайте возьмём и дружно все вместе изобретём велосипед?

Излогаю идею. Компутер штука страшная. Ассемблер и програмирование на нём - штука ещё более страшная. Тогда как машина Тюринга проста как пять копеек, а програмирование имеет изюминку, ибо для успешного програминга этой АВМ нужен логически-извращённый мозг (одна штука) и ничего больше. Это причина номер раз.

Причина номер два. По закону как бишь там его.. короче вычислительные мощности машин которые стоят у нас на/под/рядом со столами растут невероятными темпами. Тем не менее - исполнение простейшей "Хелло ворлд", на каждом следующем витке развития компутерной техники, обузданной очередным исчадьем Виндовса занимает всё больше и больше времени. Позвольте господа, как же так - мощности удвоились, четырёхъядерные процессоры стоят, а тормозит в два раза больше? Не-не-не дейвид блейн, настоящие кулхацкеры всё свободное время имеют свой линукс, а над чем морально извращаться нам - электроникам и радиолюбителям?

Посему предлагаю, хрен с ним - с програмингом,- сделаем свою железяку, которая будет работать так как мы её сделаем и делать то что мы туда упихаем, без пиксельных шейдеров, без синхронизации ядер, без вирусов-антивирусов и прочая фигня... Далее изложу теорий для тех кто впервые слышит про альтернативные архитектуры.

Реклама

MyTHbIu

ну, господин хороший, боюсь зело глубоко копаете, не думаю что будет огромная активность, а если и будет, то закончится все насловах... это непросто и требует времени, которого критически мало... желаю вам успехов, ну и выкладывайте продолжение...

Реклама

thunder87l

На крайняк, ежели какой одиннадцатикласник возьмёт этот тема за реферат по информатике - тож сойдёт. Я лично жалею что школьная программа информатики не содержит даже упоминания о таком прекрасном способе сломать мозг себе и другим.

thunder87l

Итак - зе гранд теорий.

АВМ Тюринга состоит из трёх основных компонентов:

1) таблица директив (собственно программа)
2) лента, бесконечная в обоих направлениях (а как жеж - машина абстрактная)
3) автомат Тюринга выполняющий директиву

см. картинку

Реклама

thunder87l

Директива выглядит примерно вот так: C, M, S и выполняется по порядку

C - символ который следует записать в ту клетку ленты, напротив которой автомат находится

M - куда передвинуться (автомат Тюринга может двинуться на шаг вправо, на шаг влево и остаться на месте R(ight), L(eft), N(one) - соответственно)

S - состояние в которое следует перейти автомату. Для пущей визуализации представим состояния цветами.

Итак директива D, R, Green будет выполняться следующим образом:

1) Написать в клеточке букву Д
2) передвинуться на шаг вправо
3) окраситься в зелёный цвет

после выполнения этой директивы, автомат смотрит какая буква находится в той клетке напротив которой он стоит. Кроме того - он находится в сотоянии "зелёный". По этим двум критериям он находит в таблице следующую директиву, считывает её и начинает выполнять.

Это и есть всё то, что делает машина Тюринга. Согласитесь - теория не то чтобы очень много весит. Тем не менее потенциал такой машины огромен, ибо машина Тюринга по определению может выполнить любой алгоритм, а значит - она может выполнить любой алгоритм, который может выполнить персональный компьютер, будь то функции калькулятора, трёхмерного редактора, фотошопа, виндовса, и будь чего угодно.

Реклама

thunder87l

Програминг машины тюринга вещь нетривиальная и порядочно интересная, и владеть им довольно сложно научиться без рабочего прототипа самой машины. Останавливаться подробнее на этом пункте я не буду - найти програмы и наглядные симуляции их действия можно в интернете.

Итак - начнём мозговать как бы нам эту радость в жизнь вооплотить. Ключевой элемент тут безусловно - директива. Возьмём размер директивы в один байт. Восемь битов вполне сойдут для наших целей на начальном уровне. Вопрос в том - как их распределить.

[0] [1] [2] [3] [4] [5] [6] [7]

О, забыл сказать. Машина Тюринга имеет команду остановки. Команда остановки - 1) писать в клетку то число, которое в ней уже написано 2) не двигаться 3) изменить состояние на то, в котором машина уже находится.

Что эта команда делает. Автомат стоит на одном месте и бесконечно переписывает одну и ту-же букву. Бесконечная рекурсия и есть состояние остановки для машины Тюринга.

Где это используется. Допустим у вас есть калькулятор. Вы набираете нужные числа, и путём скрытых от глаза операций получаете ответ - всё, стоп. Больше он ничего делать не должен - он ничего не считает, ничего не пишет - результат получен и точка - автомат остановился.

К чему я это всё. Дело в том, что это единственный случай, в котором реально используется команда "не двигаться". И в принципе её можно заменить на пару команд "двигаться вправо и ничего не делать" + "двигаться влево и ничего не делать", которые образуют всё ту-же бесконечную рекурсию. Что конкретно это нам даёт. Вместо трёх команд на движение мы имеем только две - итого для записи движения нам вместо двух потребуется всего один бит.

0b - движение (0 - влево, 1 - вправо). Бит передвижения мы запишем первым.

Реклама

Pa5ha

Негоже 1-го января там мозг иметь.

Тем не менее. В свою бытность "каким-нибудь одинадцатиклассником" писал машину тьюринга на дельфи. А то так бы и писали программы на бумажке дальше

http://turing.narod.ru , если ещё не удалили. давно там небыл

thunder87l

Я оч рад за вас что вы писали машину Тюринга в 11 классе, но в одном Австралийском универе в начале этого тысячелетия группа из трёх (кажется трёх..) студентов защитили бакалаврскую написав и оформив эмулятор Intel 8008, который строением не намного сложнее. При чём они это делали имея всю документацию.

Pa5ha

Я рад за них. А зачем они это сделали?

thunder87l

Итак, продолжим. Оставшиеся семь битов поделим следующим образом: 3 - на символы, 4 - на состояния автомата. В перспективе - количество букв увеличивает функциональность машины, а количество состояний - максимальную длинну программы. Соответственно, чтобы напрограмить хоть что-нибудь более или менее связное нам вполне хватит 8 букав и 16 строк.

Теперь конкретно к железу. Плясать начинаем от программы. Таблица АВМ - блок памяти SRAM, где каждая ячейка занята директивой. Буквы и состояния вместе - адрес ячейки. Итого память имеет 7 адресных входов. Соответственно для реализации памяти нам необходим камень SRAM 128x 8-бит.

Что касается ленты памяти. Поскольку наша машина даёт только команды влево и вправо, и непосредственно к адресу не обращается - длинна ленты (количество памяти) не зависит от первого компонента. Сделаем её 256x4bit. Вообще реально заняты у нас будут три бита, но на три вряд ли можно найти необходимый компонент. Итак SRAM 256x 4-бит.

thunder87l

Читаем вдумчиво - БАКАЛАВРСКУЮ защищали.

thunder87l

Behold!! Вот так оно по идее выглядит:

thunder87l

Что есть что и как оно должно работать.

PM - программа, собственно - таблица директив

OM - оперативная память, ака лента

M - логическое устройство добавляющее единицу или отнимающее единицу от адреса

DAT, ADR, DIR, ST - регистры в которых хранится информация

DAT x4-bit
ADR x8-bit
ST x4-bit
DIR x8-bit

CON - контроллер, логическое устройство контролирующее работу всех компонентов.

thunder87l

Теперь о регистрах.

Вот где я не врубаюсь - там не врубаюсь, признаюсь честно. Как называется такой тип регистра и тем более - где его купить, я факин не в курсе.

На рисунке примерно указаны 1) как оно выглядит и 2) как оно подключается.

Что оно делает? Оно запоминает сигнал когда сигнал "read" спадает и транслирует запомненый сигнал пока сигнал "write' высокий.

thunder87l

Итак, вопрос на миллион долларов - способно ли это устройство выполнять функции автомата Тюринга?

Опишу всю схему действия с помощью вот таких записей:
устройство > шина: устройство транслирует сигнал на шину
устройство < шина: устройство запоминает сигнал с шины
устройство X шина: устройство отключено от шины

Соответственно этими функциями оперирует контроллер, следовательно в конкретный момент мы собственно определяем логику контроллера.

thunder87l

Итак что делает машина Тюринга.

Функция 1: найти директиву по состоянию и символу.

ADR > adress bus
OM <adress> data bus
DAT < data bus
DAT x data bus
OM x data bus
OM x adress bus
ADR x ardess bus

так, вот тут я немного попарился с рисунком... Там где PM соединяется тремя шинами с DIR - это мы назовём directive bus и в тех местах где шина директив соединяется со state bus, data bus и жилой идущей к устройству М, надо поставить прерыватели (назовём их S от switch), чтобы сигнал идущий по линии директивы не транслировался на остальную схему, пока S=1

Пологаю что S - удобнее будет выполнить тремя транзисторами

thunder87l

Значит дальше.

S=1
DAT > data bus
ST > state bus
PM < data bus
PM <state> directive bus
DIR < directive bus
DIR x directive bus
PM x data bus
PM x state bus
PM x directive bus
ST x state bus
DAT x data bus
S=0

итог этих манипуляций - в ADR хранится текущий адрес, в DAT - символ на ленте, в DIR - директива к исполнению автоматом

thunder87l

Функция 2: выполняем директиву

DIR > directive bus
ST < state bus (directive bus)
DAT < data bus (directive bus)
M <directive> adress bus
M <adress> adress bus
ADR <adress> adress bus
DAT > data bus
OM < adress bus
OM < data bus
OM x adress bus
OM x data bus
ADR x adress bus
DAT x data bus (Это мы записали символ на ленту)

Итог: в ST хранится изменённое состояние, в ADR хранится новый адрес, в OM старый символ был переписан на новый

thunder87l

Вот собственно и весь алгоритм работы. Из одного устройства подать на линию. С линии принять регистром. С регистра передать на другое устройство. При чём если использовать немножко другую конструкцию - факт, что можно количество операций уменьшить вдвое, просто надо какую недельку поебстись и подумать на досуге что и где можно куда переставить. Кроме всего, я ещё не подумал как бы так извратиться и перегонять по разным жилам данные одновременно, что позволило бы уменьшить количество тактов для выполнения программы.

В общем - оно работает. Далеко не идеально, оптимизировать - переоптимизируешься, но факт - оно работает. Следовательно я не просто так гребал вам моск. Уря. Впрочем в первую очередь перед тем как что-либо оптимизировать и настраивать - надо подумать над устройством таинственного элемента М.

thunder87l

Думаем над девайсом М: