Где взять программы Тьюринга и Маркова?

Думаю, вопрос интересует многих. Где можно скачать или найти Машину Тьюринга и(или) Маркова? Хотелось бы решить какую-нибудь задачку(ведь не дождешься от старосты, как обычно).

Диск с машинами Тьюринга, Маркова, Поста, ... скоро будет распостранён через старост. Одна из причин задержки -- необходимость исправления старых программ под быстрые процессоры и под среду XP/2000. А пока Вы можете зайти в 438 Б "ГУК" и запустить tu4 или nam. Понедельник и суббота с 9:00 до 18:00, четверг с 9:00 до 12:00 и с 15:00 до 18:00. Если у Вас хорошо читающий CD ROM, то прошлогодний слегка сбоящий диск можно получить прямо сейчас.

А вы не могли бы скинуть интерпрЕтатор Машины Тьюринга для юникса(я так понимаю в исходниках) мне на е-майл?

Никита! Попробуйте tu03.exe, вложение к письму "Turing inside!"

Этот для доса наверное, а я просил для юникса в исходниках.

Никита! Исходник для UNIX я быстро не найду, да и авторов надо бы спросить, мы его раньше не раздавали. Попробуем проверить её работу в UNIX на платформе Intel, и, может быть, успеем записать на диски. Скажите, какой у Вас UNIX и мы подготовим выполнимый файл.
* * *
Тот exe-шник работает в XP, мы его на лекции показывали!

Red Hat Linux 9 , 5.2

По-моему написать машину Тьюринга не сложно самому. Я поспрашивал у народа: оказалось что в моей группе есть пара программистов.

Предлагаю устроить конкурс на лучшую машину Тьюринга - шлите мне на ai0@istra.ru свои проги(лучше - с исходниками, а еще лучше - с лицензией GPL ), победителя как-нибудь выберем и объявим.

От Сан Саныча проступила безумная идея: написать Машину Тьюринга на машине Тьюринга(страшный челдовек) Тому кто это сделает первое место гарантировано!(Лично я вам советую: не мучайтесь!)

А для Win32 программы принимаются?

Это все круто тока дайте плиз точное описание этой машины
Чтоб все фишки были расписаны что да как она делает

Вчера была лаба по МТ и у меня была задача, где надо было прибавить к шестнадцатеричному числу 1, если делать ее нормированно, то надо копировать это число, но поскольку на терминалах нельзя писать >147 команд, то скопировать нельзя было чисто физически(было необходимо > 200 команд). Вопрос: Где мы будем писать эти задачи на экзаменах?(Ведь если на терминалах, то получается, что есть "нерешаемые" задачи)

St. Легион! В методичке по работе № 5 есть пункт про длинные программы, их надо отлаживать в X Window System с помощью той же tu4 или в среде Windows посредством программ tu0x из CD-хрестоматии! Ограничение на самом деле весьма полезно(краткость -- сестра таланта!). Поработайте над алгоритмом! Ещё один вариант -- строго доказать(как теорему!), что Ваш алгоритм с(или без) нормировкой нереализуем на МТ в 4-ках при ограничении их числа 168. После такой таксономии алгоритма Вам могут разрешить сделать ненормированную программу, или перейти на 5-ки, но могут и пересадить на X-терминал.

А. Измайлову и др.
Написать простой эмулятор МТ на Паскале -- тема одного из заданий Практикума на ф-те ВМК. Многие наши первокурсники писали неплохие интерактивные программы МТ. Один даже сделал это на Excel'е! Мы считаем, что лучше изучать алгоритмическую модель Тьюринга непосредственно на ней, для чего и предлагаем вам лабораторные работы № 5 и 6.
Далее в лекциях будет изложена более наглядная и компактная версия алгоритмической модели Тьюринга, которая пригодна и для контрольной работы, и для экзамена. Отладки программ на экзаменах не будет. Это значительно превышает нормы трудоёмкости экзамена (15-18 мин. на человека). Кроме того, информатика в школах преподаётся как правило плохо, не является предметом вступительных экзаменов и 70% первокурсников не имеют необходимых знаний и навыков даже в рамках школьной программы. Поэтому в экзаменационной обстановке требовать от студента отладки программы и её успешного тестирования мы пока не можем. Экзамен проходит в простой письменной форме.
Что касается написания МТ на МТ, идея не нова, она была в 30-50-х гг. прошлого века исследована математиками в общем виде, на кончике пера. Это так называемая универсальная машина Тьюринга, доказавшая принципиальную возможность построения абсолютно универсального вычислительного устройства, способного выполнять любые алгоритмы по их линейным текстовым описаниям. Эти вопросы входят в наш курс, а также рассматриваются в курсе дискретной математики (2-3 семестры).

Демо версию моего варианта МТ под windows можно скачать на
imonakov.narod.ru. Полная версия может быть скоро будет.

Я подумал на тему об алгоритме, и пришел к выводу что МТ это такая вешь на которой особо много алгоритмов не напишешь(т.е. если существует рациональное решение, то альтернативных к нему решений практически нет)... :-(

St. Легион! И на ассемблере тоже много не напишешь! Поэтому на нём мало кто сейчас пишет, разве что наиболее ресурсоёмкие места, выявленные профилёром программ на языках высокого уровня, переписывают. Но личный опыт написания микрокода необходим. Тренировка -- тоже. Одна моя ученица(будучи уже кандидатом физ.-мат. наук) написала и отладила на 386-м лаптопе с 2 Мбайтами памяти 15 программ за вечер, пока её маленький ребёнок спал!
Насчёт алгоритма -- не зарекайтесь, лучшее -- злейший враг хорошего!

[radik.narod.ru] - МТ под Win32

[semillon.wpi.edu]
[sourceforge.net]
[www.cheransoft.com]

Кстати этот вопрос на лекциях не поднимался...

A physical Turing machine

It is not difficult to simulate a Turing machine on a modern computer (except for the limited memory of actually existing computers).

It is also possible to build a Turing machine on a purely mechanical basis. The mathematician Karl Scherer has indeed built such a machine in 1986 using metal and plastic construction sets, and some wood. The 1.5 meter high machine uses the pulling of strings to read, move and write the data (which is represented using ball bearings).

The machine is now exhibited in the entrance of the Department of Computer Science of the University of Heidelberg, Germany.

Also, using a few hundred mirrors, one can build an optical universal Turing machine in one's backyard, using the Horseshoe map. This is based on a work by Stephen Smale.

The concept of a Turing machine was used as an educational tool in the science fiction novel, The Diamond Age (1995), by Neal Stephenson. The main character, Nell, possesses an interactive book which teaches her creative thinking and logic by presenting puzzles in a story as Turing machines which become more and more complex as the story progresses. They begin as a simple chain-fed clockwork device and progresses to abstract economic processes, trades, and finally the interaction of entire fictional kingdoms.

zzz, спасибо за хорошие советы(обязательно ими воспользуюсь!) Созрел еще один вопрос: С чем связано то, что мы работаем на МТ "в четверках", а не "в пятерках"? Ведь, насколько я понял, именно "в пятерках" можно написать очень рациональное решение(ядреный алгоритм составить).

St. Легион! Как было сказано на лекции, четвёрки -- это RISC-архитектура, а пятёрки -- CISC! Со всеми вытекающими последствиями.
Одна из наиболее удачных книг по Тьюринговской теории алгоритмов(под ред. Эббинхауза, см. список литературы), которой мы сейчас следуем, излагает МТ в 4-ках.
Ну а RISC-архитектура настолько эффективна, что при существенно меньшей частоте даёт бОльшую производительность. И всё это несмотря на то, что количество команд в программах для RISC-процессоров в 3-4 раза больше!

На самом деле, программы МТ можно записывать по-разному; пятерки или четверки - это только один из возможных способов. Можно представлять программу в виде таблицы (по вертикали и горизонтали - читаемые головкой символы и состояния), в виде графа состояний и переходов и т.д. Четверки/пятерки удобны как линейная запись программы.

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

>>Кстати этот вопрос на лекциях не поднимался...
>>A physical Turing machine

Да, я только сказал, что представляю себе МТ как кассовый аппарат начала прошлого века с блестящими никелированными и деревянными лакированными ручками, издающий звуки вроде Пинк Флойдовского фона к "Money", и что надо бы, конечно, сделать соответствующую мультимедийную анимацию.

У меня 9 задание по 5 лабе.Там надо к числу прибавить 1.
Как должна выглядеть лента до начала работы программы и после.
л-лямбда
Я думаю так:
до л[число_1]
после л [число_1+1]
Я прав?Ответьте поскорее хочется побыстрей доделать эту лабу.

>>Как должна выглядеть лента до начала работы программы и после?

Стандартно! Нотацию см. в лекциях и в задании к работе №5.

[лw(л)л> =*> [лwлw'(л)л>, ф_16(w')=ф_16(w)+1

Никита! У меня тоже 9 задание, его обсуждение см. ниже. У многих людей возникли вопросы по зачету, особенно интересно узнать дату его проведения. Кстати эксперимент с "машинным e" мне не удался(у меня TP 7.1 Final), т.к. в ответе пишется не больше 12 знаков после запятой, и они, соответственно, все нули...

St.Легион!Каким алгоритмом ты копируешЬ слово?В моем алгоритме для копирования
мне понадобит ся(я не стал писать ТАК много команд) более 576 строк(учитывая что алфавит состоит из 16 разных символов)!!!
В общих словах алгоритм такой:

я сдвигаю каретку на самую левую БУКВУ слова
(2)перевожу головку в состояние соответствующее этой БУКВЕ
БУКВУ заменяю на Х
(3)перехожу направо до первой свободной ЯЧЕЙКИ(>16 команд)
пишу БУКВУ
перехожу в другое состояние соответсвующее этой БУКВЕ
(4)перехожу назад к Х(>16 команд) и заменяю его на бывший ЗНАК
сдвиг вправо и снова щаг 2
-----------------------
тепер я посчитал у меня 16 разных БУКВ алфавита на каждый ЗНАК
надо сделать пункты 3 и 4 с разными сОстояниями, т.е. это где-то 32 команды,
НО ведь БУКВ-то 16 т.е. 16*32=576!!!!!!!!!!!!!!!!!!!!!
+алгоритм увеличения на единицу но он не большой <50 команд
--------------------------------------------------
Если кто знает другие алгоритмы подскажите, я пока не придумал.....

Ещё
[rain.ifmo.ru]
и ещё
[rain.ifmo.ru]

Ершов А.С. aka Vikont!
Неплохо, выглядит правдоподобно. Правда на Прологе или на Рефале это на порядок короче. А как насчёт разработки универсального алгоритма Маркова, подобного УМТ? Что-то мне такая мысль раньше не приходила в голову!
Куда пропали лексемы из программы я не знаю, может какие-то комбинации знаков этого птичьего языка совпали с директивами форматирования?

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

; НАМ - интерепритатор нормальных алгоритмов Маркова
(setq sp1 ())
(setq sp2 ())
(setq sp3 ())
(terpri)
(princ "Введите путь к файлу программы: ")
(with-open-file (stream (read))
(do ((line (read-line stream nil)
(read-line stream nil)))
((null line))
(setq sp1 (cons (subseq line 0 (position #\ line)) sp1))
(setq sp2 (cons (subseq line (+ 1 (position #\ line)) (position #\ line
:from-end t)) sp2))
(setq sp3 (cons (subseq line (+ 1 (position #\ line :from-end t)) (length
line)) sp3))
)
)
(print (setq sp1 (reverse sp1)))
(print (setq sp2 (reverse sp2)))
(print (setq sp3 (reverse sp3)))
(terpri)
(princ "Введите начальное состояние ленты НАМ: ")
(setq line (read))

(defun sub (old new)
(let ((part1) (part3))
(cond
((numberp (search old line))
(progn
(setq part1 (subseq line 0 (search old line)))
(setq part3 (subseq line (+ (length old) (search old line)) (length line)))
(concatenate 'string part1 new part3)
))
(t line)))
)

(defun nam (old flag new)
(progn
(setq buffer line)
(cond
((string= buffer (setq line (sub (car old) (car new))))
(nam (cdr old) (cdr flag) (cdr new))) ; вот она - рекурсия
(t (progn
(print line)
(if (string= (car flag) "->.")
(setq line (sub (car old) (car new)))
(nam sp1 sp2 sp3))))
)
)
)

(nam sp1 sp2 sp3)
(print line)

Тем не мение я сделал несколько выводов о языке Common Lisp и хочу подельтся
ими с интересующимися.
1)
Хорошой литературы по языку на русском нет - полный бред написан в книге
"Основы функционального программирования" (Л.В. Городня), читать ее во всяком с
лучае было "ну очень" тяжело - ни описания языка, ни практических советов по
решению задач - только сухая теория на непонятном языке. Книга "Мир Лиспа" т.1
от 1990 года дает представление о языке, но информации о функциях языка в ней
крайне мало. И всеже как стправочник ее использовать можно. До Люгера мои руки
еще не дотянулись - но судя по примерам решаемых задач "введением в Лисп" там и
не пахнет.
Пришлось gogli'ть:
The Common Lisp Cookbook
Common Lisp the Language, 2nd Edition
вот то что действительно подходит для начала практического изучения языка.
2)
Сам язык и принципы функционального программирования оставили приятное
впечатление - относительно легко работать со строками, считывать информации из
файлов в списки и работать с ними. Вообще после написания программы NAM осталось
желание реализовать на Лиспе, что-то особенное, новое и интересное.
3)
Неприятным осадком на душе остается ощущение полного программистского
"underground"а в отношении языка. Особенно это было видно по реакции рунета на
запросы о Лиспе.
Короче вопросов оталось больше чем полученных ответов, но в целом Лисп - штука
интересная, особенно для общего развития, и как способ поэксперементировать с
различными теоритическими моделями программирования.

Отвечая на (3)-й пункт: язык LISP действительно является Underground-ом у нас, поскольку Российская система образования больше тяготеет к Европейской, где любят логику и логическое программирование (вероятно, это берет начало в Бурбаковских традициях формализации математики). В США Лисп намного популярнее, поскольку он входит в состав любого приличного универститетского образования в области информатики, и зачастую вытекает из теории вычислимости, в основе которой лежит лямбда-исчисление (в отличие от машин Тьюринга у нас).

К тому же, у языка Лисп появилось множество наследников в виде более современных функциональных языков: Scheme, Haskell и ML (SML). Community соответствующих языков весьма широкие, хотя, опять же, не у нас в стране. У нас почему-то считается, что С++ спасет мир...

С уважением,

Сошников Д.В.

Ребят, я может не в тему!!!! Но не подскажете где взять реферат на тему "Машина Тьюринга (или Поста)"

Девчат, в тему!

Книжка для школьников.
В.А. Успенский. Машина Поста. --М.: Наука, 1979.
<Отсканированная в формате djvu есть на сайте МЦНМО>

Книжка для студентов.
Машины Тьюринга и рекурсивные функции."Современная математика". Популярная серия. --М.: Мир, 1972

Где пробить Реферат "Машины Тьюринга"??????????Оля писал(а):

> Ребят, я может не в тему!!!! Но не подскажете где взять реферат
> на тему "Машина Тьюринга (или Поста)"