Машина Тюринга
Вт дек 30, 2008 23:17:50
Господа любители паять железяки и извращаться с цифровой логикой, а давайте возьмём и дружно все вместе изобретём велосипед?
Излогаю идею. Компутер штука страшная. Ассемблер и програмирование на нём - штука ещё более страшная. Тогда как машина Тюринга проста как пять копеек, а програмирование имеет изюминку, ибо для успешного програминга этой АВМ нужен логически-извращённый мозг (одна штука) и ничего больше. Это причина номер раз.
Причина номер два. По закону как бишь там его.. короче вычислительные мощности машин которые стоят у нас на/под/рядом со столами растут невероятными темпами. Тем не менее - исполнение простейшей "Хелло ворлд", на каждом следующем витке развития компутерной техники, обузданной очередным исчадьем Виндовса занимает всё больше и больше времени. Позвольте господа, как же так - мощности удвоились, четырёхъядерные процессоры стоят, а тормозит в два раза больше? Не-не-не дейвид блейн, настоящие кулхацкеры всё свободное время имеют свой линукс, а над чем морально извращаться нам - электроникам и радиолюбителям?
Посему предлагаю, хрен с ним - с програмингом,- сделаем свою железяку, которая будет работать так как мы её сделаем и делать то что мы туда упихаем, без пиксельных шейдеров, без синхронизации ядер, без вирусов-антивирусов и прочая фигня... Далее изложу теорий для тех кто впервые слышит про альтернативные архитектуры.
Излогаю идею. Компутер штука страшная. Ассемблер и програмирование на нём - штука ещё более страшная. Тогда как машина Тюринга проста как пять копеек, а програмирование имеет изюминку, ибо для успешного програминга этой АВМ нужен логически-извращённый мозг (одна штука) и ничего больше. Это причина номер раз.
Причина номер два. По закону как бишь там его.. короче вычислительные мощности машин которые стоят у нас на/под/рядом со столами растут невероятными темпами. Тем не менее - исполнение простейшей "Хелло ворлд", на каждом следующем витке развития компутерной техники, обузданной очередным исчадьем Виндовса занимает всё больше и больше времени. Позвольте господа, как же так - мощности удвоились, четырёхъядерные процессоры стоят, а тормозит в два раза больше? Не-не-не дейвид блейн, настоящие кулхацкеры всё свободное время имеют свой линукс, а над чем морально извращаться нам - электроникам и радиолюбителям?
Посему предлагаю, хрен с ним - с програмингом,- сделаем свою железяку, которая будет работать так как мы её сделаем и делать то что мы туда упихаем, без пиксельных шейдеров, без синхронизации ядер, без вирусов-антивирусов и прочая фигня... Далее изложу теорий для тех кто впервые слышит про альтернативные архитектуры.
Ср дек 31, 2008 00:05:23
ну, господин хороший, боюсь зело глубоко копаете, не думаю что будет огромная активность, а если и будет, то закончится все насловах... это непросто и требует времени, которого критически мало... желаю вам успехов, ну и выкладывайте продолжение...
Ср дек 31, 2008 09:31:30
На крайняк, ежели какой одиннадцатикласник возьмёт этот тема за реферат по информатике - тож сойдёт. Я лично жалею что школьная программа информатики не содержит даже упоминания о таком прекрасном способе сломать мозг себе и другим.
Ср дек 31, 2008 09:48:29
Итак - зе гранд теорий.
АВМ Тюринга состоит из трёх основных компонентов:
1) таблица директив (собственно программа)
2) лента, бесконечная в обоих направлениях (а как жеж - машина абстрактная)
3) автомат Тюринга выполняющий директиву
см. картинку
АВМ Тюринга состоит из трёх основных компонентов:
1) таблица директив (собственно программа)
2) лента, бесконечная в обоих направлениях (а как жеж - машина абстрактная)
3) автомат Тюринга выполняющий директиву
см. картинку
Чт янв 01, 2009 20:12:41
Директива выглядит примерно вот так: C, M, S и выполняется по порядку
C - символ который следует записать в ту клетку ленты, напротив которой автомат находится
M - куда передвинуться (автомат Тюринга может двинуться на шаг вправо, на шаг влево и остаться на месте R(ight), L(eft), N(one) - соответственно)
S - состояние в которое следует перейти автомату. Для пущей визуализации представим состояния цветами.
Итак директива D, R, Green будет выполняться следующим образом:
1) Написать в клеточке букву Д
2) передвинуться на шаг вправо
3) окраситься в зелёный цвет
после выполнения этой директивы, автомат смотрит какая буква находится в той клетке напротив которой он стоит. Кроме того - он находится в сотоянии "зелёный". По этим двум критериям он находит в таблице следующую директиву, считывает её и начинает выполнять.
Это и есть всё то, что делает машина Тюринга. Согласитесь - теория не то чтобы очень много весит. Тем не менее потенциал такой машины огромен, ибо машина Тюринга по определению может выполнить любой алгоритм, а значит - она может выполнить любой алгоритм, который может выполнить персональный компьютер, будь то функции калькулятора, трёхмерного редактора, фотошопа, виндовса, и будь чего угодно.
C - символ который следует записать в ту клетку ленты, напротив которой автомат находится
M - куда передвинуться (автомат Тюринга может двинуться на шаг вправо, на шаг влево и остаться на месте R(ight), L(eft), N(one) - соответственно)
S - состояние в которое следует перейти автомату. Для пущей визуализации представим состояния цветами.
Итак директива D, R, Green будет выполняться следующим образом:
1) Написать в клеточке букву Д
2) передвинуться на шаг вправо
3) окраситься в зелёный цвет
после выполнения этой директивы, автомат смотрит какая буква находится в той клетке напротив которой он стоит. Кроме того - он находится в сотоянии "зелёный". По этим двум критериям он находит в таблице следующую директиву, считывает её и начинает выполнять.
Это и есть всё то, что делает машина Тюринга. Согласитесь - теория не то чтобы очень много весит. Тем не менее потенциал такой машины огромен, ибо машина Тюринга по определению может выполнить любой алгоритм, а значит - она может выполнить любой алгоритм, который может выполнить персональный компьютер, будь то функции калькулятора, трёхмерного редактора, фотошопа, виндовса, и будь чего угодно.
Чт янв 01, 2009 20:44:01
Програминг машины тюринга вещь нетривиальная и порядочно интересная, и владеть им довольно сложно научиться без рабочего прототипа самой машины. Останавливаться подробнее на этом пункте я не буду - найти програмы и наглядные симуляции их действия можно в интернете.
Итак - начнём мозговать как бы нам эту радость в жизнь вооплотить. Ключевой элемент тут безусловно - директива. Возьмём размер директивы в один байт. Восемь битов вполне сойдут для наших целей на начальном уровне. Вопрос в том - как их распределить.
[0] [1] [2] [3] [4] [5] [6] [7]
О, забыл сказать. Машина Тюринга имеет команду остановки. Команда остановки - 1) писать в клетку то число, которое в ней уже написано 2) не двигаться 3) изменить состояние на то, в котором машина уже находится.
Что эта команда делает. Автомат стоит на одном месте и бесконечно переписывает одну и ту-же букву. Бесконечная рекурсия и есть состояние остановки для машины Тюринга.
Где это используется. Допустим у вас есть калькулятор. Вы набираете нужные числа, и путём скрытых от глаза операций получаете ответ - всё, стоп. Больше он ничего делать не должен - он ничего не считает, ничего не пишет - результат получен и точка - автомат остановился.
К чему я это всё. Дело в том, что это единственный случай, в котором реально используется команда "не двигаться". И в принципе её можно заменить на пару команд "двигаться вправо и ничего не делать" + "двигаться влево и ничего не делать", которые образуют всё ту-же бесконечную рекурсию. Что конкретно это нам даёт. Вместо трёх команд на движение мы имеем только две - итого для записи движения нам вместо двух потребуется всего один бит.
0b - движение (0 - влево, 1 - вправо). Бит передвижения мы запишем первым.
Итак - начнём мозговать как бы нам эту радость в жизнь вооплотить. Ключевой элемент тут безусловно - директива. Возьмём размер директивы в один байт. Восемь битов вполне сойдут для наших целей на начальном уровне. Вопрос в том - как их распределить.
[0] [1] [2] [3] [4] [5] [6] [7]
О, забыл сказать. Машина Тюринга имеет команду остановки. Команда остановки - 1) писать в клетку то число, которое в ней уже написано 2) не двигаться 3) изменить состояние на то, в котором машина уже находится.
Что эта команда делает. Автомат стоит на одном месте и бесконечно переписывает одну и ту-же букву. Бесконечная рекурсия и есть состояние остановки для машины Тюринга.
Где это используется. Допустим у вас есть калькулятор. Вы набираете нужные числа, и путём скрытых от глаза операций получаете ответ - всё, стоп. Больше он ничего делать не должен - он ничего не считает, ничего не пишет - результат получен и точка - автомат остановился.
К чему я это всё. Дело в том, что это единственный случай, в котором реально используется команда "не двигаться". И в принципе её можно заменить на пару команд "двигаться вправо и ничего не делать" + "двигаться влево и ничего не делать", которые образуют всё ту-же бесконечную рекурсию. Что конкретно это нам даёт. Вместо трёх команд на движение мы имеем только две - итого для записи движения нам вместо двух потребуется всего один бит.
0b - движение (0 - влево, 1 - вправо). Бит передвижения мы запишем первым.
Пт янв 02, 2009 05:34:16
Негоже 1-го января там мозг иметь.
Тем не менее. В свою бытность "каким-нибудь одинадцатиклассником" писал машину тьюринга на дельфи. А то так бы и писали программы на бумажке дальше
http://turing.narod.ru , если ещё не удалили. давно там небыл
Тем не менее. В свою бытность "каким-нибудь одинадцатиклассником" писал машину тьюринга на дельфи. А то так бы и писали программы на бумажке дальше
http://turing.narod.ru , если ещё не удалили. давно там небыл
Пт янв 02, 2009 18:36:20
Я оч рад за вас что вы писали машину Тюринга в 11 классе, но в одном Австралийском универе в начале этого тысячелетия группа из трёх (кажется трёх..) студентов защитили бакалаврскую написав и оформив эмулятор Intel 8008, который строением не намного сложнее. При чём они это делали имея всю документацию.
Пт янв 02, 2009 18:51:18
Я рад за них. А зачем они это сделали?
Пт янв 02, 2009 19:04:58
Итак, продолжим. Оставшиеся семь битов поделим следующим образом: 3 - на символы, 4 - на состояния автомата. В перспективе - количество букв увеличивает функциональность машины, а количество состояний - максимальную длинну программы. Соответственно, чтобы напрограмить хоть что-нибудь более или менее связное нам вполне хватит 8 букав и 16 строк.
Теперь конкретно к железу. Плясать начинаем от программы. Таблица АВМ - блок памяти SRAM, где каждая ячейка занята директивой. Буквы и состояния вместе - адрес ячейки. Итого память имеет 7 адресных входов. Соответственно для реализации памяти нам необходим камень SRAM 128x 8-бит.
Что касается ленты памяти. Поскольку наша машина даёт только команды влево и вправо, и непосредственно к адресу не обращается - длинна ленты (количество памяти) не зависит от первого компонента. Сделаем её 256x4bit. Вообще реально заняты у нас будут три бита, но на три вряд ли можно найти необходимый компонент. Итак SRAM 256x 4-бит.
Теперь конкретно к железу. Плясать начинаем от программы. Таблица АВМ - блок памяти SRAM, где каждая ячейка занята директивой. Буквы и состояния вместе - адрес ячейки. Итого память имеет 7 адресных входов. Соответственно для реализации памяти нам необходим камень SRAM 128x 8-бит.
Что касается ленты памяти. Поскольку наша машина даёт только команды влево и вправо, и непосредственно к адресу не обращается - длинна ленты (количество памяти) не зависит от первого компонента. Сделаем её 256x4bit. Вообще реально заняты у нас будут три бита, но на три вряд ли можно найти необходимый компонент. Итак SRAM 256x 4-бит.
Пт янв 02, 2009 19:06:49
Читаем вдумчиво - БАКАЛАВРСКУЮ защищали.
Пт янв 02, 2009 21:53:40
Behold!! Вот так оно по идее выглядит:
Пт янв 02, 2009 22:03:23
Что есть что и как оно должно работать.
PM - программа, собственно - таблица директив
OM - оперативная память, ака лента
M - логическое устройство добавляющее единицу или отнимающее единицу от адреса
DAT, ADR, DIR, ST - регистры в которых хранится информация
DAT x4-bit
ADR x8-bit
ST x4-bit
DIR x8-bit
CON - контроллер, логическое устройство контролирующее работу всех компонентов.
PM - программа, собственно - таблица директив
OM - оперативная память, ака лента
M - логическое устройство добавляющее единицу или отнимающее единицу от адреса
DAT, ADR, DIR, ST - регистры в которых хранится информация
DAT x4-bit
ADR x8-bit
ST x4-bit
DIR x8-bit
CON - контроллер, логическое устройство контролирующее работу всех компонентов.
Пт янв 02, 2009 22:14:38
Теперь о регистрах.
Вот где я не врубаюсь - там не врубаюсь, признаюсь честно. Как называется такой тип регистра и тем более - где его купить, я факин не в курсе.
На рисунке примерно указаны 1) как оно выглядит и 2) как оно подключается.
Что оно делает? Оно запоминает сигнал когда сигнал "read" спадает и транслирует запомненый сигнал пока сигнал "write' высокий.
Вот где я не врубаюсь - там не врубаюсь, признаюсь честно. Как называется такой тип регистра и тем более - где его купить, я факин не в курсе.
На рисунке примерно указаны 1) как оно выглядит и 2) как оно подключается.
Что оно делает? Оно запоминает сигнал когда сигнал "read" спадает и транслирует запомненый сигнал пока сигнал "write' высокий.
Пт янв 02, 2009 22:45:28
Итак, вопрос на миллион долларов - способно ли это устройство выполнять функции автомата Тюринга?
Опишу всю схему действия с помощью вот таких записей:
устройство > шина: устройство транслирует сигнал на шину
устройство < шина: устройство запоминает сигнал с шины
устройство X шина: устройство отключено от шины
Соответственно этими функциями оперирует контроллер, следовательно в конкретный момент мы собственно определяем логику контроллера.
Опишу всю схему действия с помощью вот таких записей:
устройство > шина: устройство транслирует сигнал на шину
устройство < шина: устройство запоминает сигнал с шины
устройство X шина: устройство отключено от шины
Соответственно этими функциями оперирует контроллер, следовательно в конкретный момент мы собственно определяем логику контроллера.
Пт янв 02, 2009 23:24:15
Итак что делает машина Тюринга.
Функция 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 - удобнее будет выполнить тремя транзисторами
Функция 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 - удобнее будет выполнить тремя транзисторами
Пт янв 02, 2009 23:29:26
Значит дальше.
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 - директива к исполнению автоматом
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 - директива к исполнению автоматом
Пт янв 02, 2009 23:40:25
Функция 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 старый символ был переписан на новый
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 старый символ был переписан на новый
Пт янв 02, 2009 23:50:23
Вот собственно и весь алгоритм работы. Из одного устройства подать на линию. С линии принять регистром. С регистра передать на другое устройство. При чём если использовать немножко другую конструкцию - факт, что можно количество операций уменьшить вдвое, просто надо какую недельку поебстись и подумать на досуге что и где можно куда переставить. Кроме всего, я ещё не подумал как бы так извратиться и перегонять по разным жилам данные одновременно, что позволило бы уменьшить количество тактов для выполнения программы.
В общем - оно работает. Далеко не идеально, оптимизировать - переоптимизируешься, но факт - оно работает. Следовательно я не просто так гребал вам моск. Уря. Впрочем в первую очередь перед тем как что-либо оптимизировать и настраивать - надо подумать над устройством таинственного элемента М.
В общем - оно работает. Далеко не идеально, оптимизировать - переоптимизируешься, но факт - оно работает. Следовательно я не просто так гребал вам моск. Уря. Впрочем в первую очередь перед тем как что-либо оптимизировать и настраивать - надо подумать над устройством таинственного элемента М.
Сб янв 03, 2009 17:20:34
Думаем над девайсом М:
