[Perl] Машина Тьюринга
| |
Gudleifr | Дата: Пятница, 29 Мая 2015, 09:10 | Сообщение # 1 |
почти ветеран
Сейчас нет на сайте
| Ни у кого не завалялась реализация на Perl Машины Тьюринга (или другого достаточно сложного конечного автомата)? Не "гольф". Скорее, нужна красивая учебно-демонстрационная. Чтобы "входными символами" могли быть сложные регулярные выражения, и было бы куда цеплять функции-триггеры, отслеживающие переход из состояния в состояние. А то у меня получается менее красиво, чем на Си.
Быдлокодеры любят повторять: "логика, убивающая мозг",- когда их пытаются заставить программировать.
|
|
| |
Tymonr | Дата: Пятница, 29 Мая 2015, 09:57 | Сообщение # 2 |
With OpenSource forever♥
Сейчас нет на сайте
| Их же полно в интернете
Если вы решили обратиться к нам за помощью, не становитесь в позицию неудачника. И не ведите себя как неудачник. Лучший способ получить быстрый и чуткий ответ, - спрашивать как победитель — спрашивать как человек умный, уверенный в себе и знающий, которому просто понадобилась помощь при решении одной конкретной проблемы. Как правильно задавать вопросы в технических форумах
|
|
| |
Gudleifr | Дата: Воскресенье, 02 Августа 2015, 09:38 | Сообщение # 3 |
почти ветеран
Сейчас нет на сайте
| Цитата Tymonr ( ) Их же полно в интернете Это только так кажется. На самом деле число тех, кто знает, что такое Машина Тьюринга, как и число умеющих красиво писать на Perl, крайне невелико.
Добавлено (30 мая 2015, 10:30) --------------------------------------------- Цитата Gudleifr ( ) число умеющих красиво писать на Perl Я в это число явно не вхожу. У меня получается какая-то хрень, в которой надо нудно отслеживать скобки и обратные косые: Код #!/usr/bin/perl
# МАШИНА: СОСТОЯНИЕ => [[СИМВОЛ, СОСТОЯНИЕ, СДВИГ], ...]
%stats = (Garbage => [["^\\\\", "Path", 0], [0, 0, 1]], Path => [["^\$", "Param", 1], ["^. ", "Param", 0], ["^\\\\", 0, 1], ["^ТЕКСТ", "Text", 1], ["^ТАБЛИЦА", "Header", 1], ["^ЗАПИСИ", "Header", 1], [0, "Garbage", 0]], Header => [["^\$", "Text", 1], [0, 0, 1]], Text => [["^\$", "Param", 1], [0, 0, 1]], Param => [["^. ", 0, 1], ["^\\\\", "Path", 0], ["^\$", "Garbage", 1], [0, "Garbage", 0]]);
# СЧИТЫВАНИЕ СИМВОЛА, ЕСЛИ ОН ЕЩЕ НЕ БЫЛ СЧИТАН
sub ready { $reading = <FI> unless $reading; return 0 unless $reading; $reading =~ s/\s*\r?\n//; return 1 }
# ОДИН ТАКТ РАБОТЫ
sub step { my $l = $stats{$state}; # СОСТОЯНИЕ foreach (@$l) { my $s = $_->[0]; # СИМВОЛ if (!$s or $reading =~ /$s/) { $p->{$state . $s}() if exists $p->{$state . $s}; # ВЫВОД $state = $_->[1] if $_->[1]; # НОВОЕ СОСТОЯНИЕ $reading = 0 if $_->[2]; # СДВИГ return } } }
# ФУНКЦИИ ВЫВОДА: СОСТОЯНИЕ.СИМВОЛ
$p1 = {"Garbage^\\\\", sub { print "Garbage-Path:", $reading, "\n" }, "Param^\\\\", sub { print "Param-Path:", $reading, "\n" }, "Garbage0", sub { print "Garbage:", $reading, "\n" }};
# СЧИТЫВАЕМ ЛЕНТУ (ФАЙЛ)
$s = shift @ARGV; $s .= ".txt"; $p = $p1; open FI, $s; $reading = 0; $state = "Garbage"; step() while ready(); close FI
Добавлено (28 июля 2015, 11:23) --------------------------------------------- Довесок:
Зачем вообще нужна МТ?
1. Во-первых и основных, для доказательства разного рода фигни "с точки зрения банальной эрудиции". 2. Во-вторых, для распознавания и преобразования строк "символов" (физическая сторона ее умственности). 3. В-третьих, для представления моделей "блуждания".
Описание МТ, кроме некоторых соглашений "о массивах" состоит из "таблицы":
(стар.состояние, стар.символ) => (нов.состояние, нов.символ, перемещение).
Варианты:
Во-первых, некоторые из перечисленных "величин", могут быть "наборами" (обозначим квадратными скобками):
1. (стар.состояние, [стар.символ]) => (нов.состояние, [нов.символ], перемещение) - машина с несколькими дорожками на ленте. 2. (стар.состояние, [стар.символ]) => (нов.состояние, [нов.символ], [перемещение]) - машина с несколькими лентами. 3. (стар.состояние, стар.символ) => (нов.состояние, нов.символ, [перемещение]) - машина с многомерной лентой. 4. (стар.состояние, стар.символ) => ([нов.состояние], нов.символ, перемещение) - недетерминированная машина. ...
Во-вторых, на множества из которых берутся "величины" можно ограничивать по-разному:
1. возможна машина только с двумя "символами" 2. возможна машина только с двумя "состояниями" 3. "перемещение" может включать или не включать действие "остаться на месте" ...
И т.д., и т.п...
Самое главное, все эти машины эквивалентны в смысле своей вычислительной мощности. Ни одна из них не лучше и не хуже. Даже существуют алгоритмы автоматического преобразование из одной типа в другую. Поэтому, если мы сможем придумать, какое либо полезное применение МТ, то привести ее к "каноническому виду" труда не составит.
Что тут можно программировать (см. выше)?
1. "Банальная эрудиция". Написать реализацию "наборов" и "таблицы". На их основе писать автоматические преобразователи из одного вида в другой. Автоматически строить машину нужного типа по "заданию" (обычно, "допускаемому языку").
2. "Символы". Задача разбора (всяких там регулярных выражений и прочих грамматик) встречается достаточно часто. Но МТ для их распознавания обычно оказывается слишком мощной. Почти всегда хватает конечных автоматов (иногда с наворотами), которые не "отматывают ленту назад".
3. "Блуждание". Рассматриваем ленту как "поток событий" или "карту местности". Тогда наша МТ представляет собой либо "автомат игры", либо "модель игрока". И мы можем попытаться вынести суждения о правильности/неправильности модели, ее избыточности и непротиворечивости. Конечно, в очень узких пределах, т.к. одна МТ (в конечном итоге, мы сами) не может предсказать поведение другой (программы).
Добавлено (02 августа 2015, 09:38) --------------------------------------------- Довесок #2: В методических целях (и чтобы поржать) переписал автомат на древнем BASIC. Осмысленные имена заменены комментариями. Для хоть какой-то наглядности программа разбита на два блока: 1000-1440 - состояний (соответствует %stats) и 2000-3690 - вывода (соответствыет sub step). Вместо ассоциативного массива код надо вставлять в соответствующие строки блока вывода - в промежутки XX00-XX90. Понятно, BASIC-программа немного более чувствительна к размеру строк и наличию в них мусора, но это поправимо (я просто не стал усложнять код). Код 1000 REM GARBAGE 1010 IF LEFT$(S$,1)="\" THEN 2000 1020 GOTO 2100 1100 REM PATH 1110 IF LEN(S$)=0 THEN 2200 1120 IF MID$(S$,2,1)=" " THEN 2300 1130 IF LEFT$(S$,1)="\" THEN 2400 1140 IF LEFT$(S$,5)="ТЕКСТ" THEN 2500 1150 IF LEFT$(S$,7)="ТАБЛИЦА" THEN 2600 1160 IF LEFT$(S$,6)="ЗАПИСИ" THEN 2700 1170 GOTO 2800 1200 REM HEADER 1210 IF LEN(S$)=0 THEN 2900 1220 GOTO 3000 1300 REM TEXT 1310 IF LEN(S$)=0 THEN 3100 1320 GOTO 3200 1400 REM PARAM 1410 IF LEN(S$)=0 THEN 3500 1420 IF LEFT$(S$,1)="\" THEN 3400 1430 IF MID$(S$,2,1)=" " THEN 3300 1440 GOTO 3600 2000 REM GARBAGE - ОБРАТНАЯ КОСАЯ - PATH 2090 GOTO 1100 2100 REM GARBAGE - ПРОЧЕЕ - GARBAGE 2190 LINE INPUT#1, S$: GOTO 1000 2200 REM PATH - ПУСТО - PARAM 2290 LINE INPUT#1, S$: GOTO 1400 2300 REM PATH - БУКВА+ПРОБЕЛ - PARAM 2390 GOTO 1400 2400 REM PATH - ОБР.КОСАЯ - PATH 2490 LINE INPUT#1, S$: GOTO 1100 2500 REM PATH - "ТЕКСТ" - TEXT 2590 LINE INPUT#1, S$: GOTO 1300 2600 REM PATH - "ТАБЛИЦА" - HEADER 2690 LINE INPUT#1, S$: GOTO 1200 2700 REM PATH - "ЗАПИСИ" - HEADER 2790 LINE INPUT#1, S$: GOTO 1200 2800 REM PATH - ПРОЧЕЕ - GARBAGE 2890 GOTO 1000 2900 REM HEADER - ПУСТО - TEXT 2990 LINE INPUT#1, S$: GOTO 1300 3000 REM HEADER - ПРОЧЕЕ - HEADER 3090 LINE INPUT#1, S$: GOTO 1200 3100 REM TEXT - ПУСТО - PARAM 3190 LINE INPUT#1, S$: GOTO 1400 3200 REM TEXT - ПРОЧЕЕ - TEXT 3290 LINE INPUT#1, S$: GOTO 1300 3300 REM PARAM - БУКВА+ПРОБЕЛ - PARAM 3390 LINE INPUT#1, S$: GOTO 1400 3400 REM PARAM - ОБР.КОСАЯ - PATH 3490 GOTO 1100 3500 REM PARAM - ПУСТО - GARBAGE 3590 LINE INPUT#1, S$: GOTO 1000 3600 REM PARAM - ПРОЧЕЕ - GARBAGE 3690 GOTO 1000 Сравнивая Perl- и BASIC-машины, мы должны сделать два вывода: * (Старые) языки программирования изначально создавались (умными людьми) как практическое воплощение всех этих "теоретических основ вычислений". И добавлять в них "еще немножко полезных абстракций и возможностей структурирования" - дело достаточно пустое, он и и так "все могут". * Препроцессор (умный редактор), который хоть как-то помог бы не запутаться в этих "номерах строк/состояний", вещь жутко необходимая.
Быдлокодеры любят повторять: "логика, убивающая мозг",- когда их пытаются заставить программировать.
Сообщение отредактировал Gudleifr - Воскресенье, 02 Августа 2015, 09:39 |
|
| |
AlexRabbit | Дата: Воскресенье, 02 Августа 2015, 10:50 | Сообщение # 4 |
старожил
Сейчас нет на сайте
| Это не поможет? http://mrob.com/pub/perl/turing.txt & http://scienceblogs.com/goodmath/2007/02/03/basics-the-turing-machine-with-1/ and btw: http://www.perlmonks.org/?node_id=809842
Сообщение отредактировал AlexRabbit - Воскресенье, 02 Августа 2015, 10:56 |
|
| |
Gudleifr | Дата: Воскресенье, 02 Августа 2015, 14:30 | Сообщение # 5 |
почти ветеран
Сейчас нет на сайте
| AlexRabbit, спасибо, надо посмотреть Добавлено (02 августа 2015, 14:30) --------------------------------------------- ... посмотрел. По первой ссылке - "обычная демонстрационная машина", основная часть кода которой предназначена для красивого ввода-вывода ленты/таблицы. Сама машина реализована по "остаточному принципу". По второй - забавная машина представляющая один такт работы как операцию макроподстановки в строку-ленту. Красиво, но не практично.
Т.е. по обоим ссылкам представлена "машина как проблема", а меня больше интересует "машина как решение".
Быдлокодеры любят повторять: "логика, убивающая мозг",- когда их пытаются заставить программировать.
|
|
| |
|