Пятница, 22 Ноября 2024, 20:19

Приветствую Вас Гость

[ Новые сообщения · Игроделы · Правила · Поиск ]
  • Страница 1 из 1
  • 1
[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)
---------------------------------------------
... посмотрел.
По первой ссылке - "обычная демонстрационная машина", основная часть кода которой предназначена для красивого ввода-вывода ленты/таблицы. Сама машина реализована по "остаточному принципу".
По второй - забавная машина представляющая один такт работы как операцию макроподстановки в строку-ленту. Красиво, но не практично.

Т.е. по обоим ссылкам представлена "машина как проблема", а меня больше интересует "машина как решение".


Быдлокодеры любят повторять: "логика, убивающая мозг",- когда их пытаются заставить программировать.
  • Страница 1 из 1
  • 1
Поиск:

Все права сохранены. GcUp.ru © 2008-2024 Рейтинг