Subject: Re: SURA: от нас с Робертом всем -- троекратное, симметричное URA!
From: Sergei M. Abramov (at home) (abram@botik.ru)
Date: Wed May 09 2001 - 16:36:59 MSD
День добрый, всем!
Я попробую начать с самого простого примера. Но может реальные УРА, и старый
и новый, уже такие, что это для них не проблема, не знаю, я исхожу из
отстоявшегося у меня с 70-х образа "простого" УРА.
Как будет ясно ниже, твой образ простого УРА намного серьезнее, чем то, что я
всегда называл УРА.
Имеем функцию
Rev {
s1 e2 = <Rev e2> s1;
=;
}
(прошу прощения, мне лень ставить точки в переменных)
Сначала рассмотрим задачу: <Rev ex> = 'abc'. Очевидно, что любой УРА с ней
легко справляется и выдает, что есть одно и только одно решение: ex = 'cba'.
Увы, УРА как он есть (без суперкомпиляции) с задачей справляться-то справляется
(ответ находит), но после этого занимается бесконечно долгой работой--той самой,
о которой ты пишешь: "потом будет бесконечно долго крутиться, пытаясь найти
другие".
Вообще говоря УРА, это вот такая композиция (я разложу композицию в let-запись):
ura prog clsio = let clsin = in_ clsio /* проекция желаемого IO-мно-
жества на ось Input */
tree = ppt p clsin /* обычное перф. дерево процессов */
graphic = tab tree clsin /* строим график программы, как
поток (ленивый список)
IO-классов */
in concat (map (*. clsio) graphic)
/* решение есть пересечение
графика
программы с желаемым
IO-множеством */
Про такую организацию УРА можно (и очень легко) доказать вот такой критерий
(стр. 26 Теорема 12 в статье):
То есть, УРА за конечное время терминируется, если время счета программы на
данных из clsin "равномерно ограничено" (I.c) константой (которая не зависит от
того, какие данные из clsin мы берем).
Именно поэтому ("равномерно ограничено", I.c), конечное время считаются любые
примеры, имеющие вид:
match [ ????? , "ABC" ] = ?????
И поэтому, УРА будет работать бесконечно и одинаково успешно на обоих примерах с
реверсом (как с одиночным, так и с вложенным).
А теперь рассмотрим задачу: <Rev <Rev ex>> = 'abc'. Как мне кажется, сидящий
у меня в голове УРА выдаст решение ex = 'abc', а потом будет бесконечно долго
крутиться, пытаясь найти другие.
Видимо, "УРА, сидящий в твоей голове" содержит элементы суперкомпиляции--если он
на одиночном реверсе завершался в конечное время. Или, как минимум, твой УРА
содержит то самое превентивное отсечение бесконечных поддеревьев, не содержащих
решений, о котором я писал в прошлом письме.
Да, для УРА с превентивным отсечением все будет так, как ты сказал: на одиноком
реверсе УРА завершится за конечное время, а на вложенном--незавершится.
И сделанная нами с Робертом смена третьей фазы и формата задачи эту пробему не
решает. Здесь требуются более серьезные инструменты. Чтобы понять какие, скажу
еще одно:
Заметим, что вложенность тут вовсе не при чем. Достаточно перейти от
выплевывающего реверса к реверсу с аккамулятором (который только в конце дает
свой ответ), чтобы получить вот что: УРА бесконечно работает как в случае с
одиночного, так и в случае вложенного реверса.
И улучшить здесь положение может только технология суперкомпиляции. Но не той
суперкомпиляции, которую все уже освоили (она ничего не даст), а той
суперкомпиляции, о которой столько лет говорят и мечтают---я говорю о ScpWalk.
PPS. Сергей, у меня одно небольшое лингвистическое предложение: слово
"лизон" по русски выглядит как-то неприлично, может лучше писать его "лиезон",
или "лиазон", как больше нравится...
1.. Алик, я абсолютно безграмотен и заание извиняюсь за опечатки в русских
(и не только) словах
2.. Мне очень кажется, что лезон (или как оно пишется?) -- уже давно (до
нас) русское (конечно заимствованное) слово, а именно--термин из рускоязычных
физико-ядерных печатных работ
Насколько я помню (ой и сильно я могу заблуждаться--все это было в далеком
детстве в школе еще): лезон--частица, ответственная за слабое (или сильное?)
взаимодействие. Есть разновидности этой элементарной частицы: пионы (пи-лезоны)
и меоны (мю-лезоны).
3.. Так что, увы, не удастся между сбою "повыбирать", как нам с вами лучше
его писать по русски. Все что нам надо, так просто узнать (у физиков, у
Нозика?), как оно пишется на самом деле в русскоязычных работах.
Удачи
Сергей
This archive was generated by hypermail 2b25 : Mon Oct 25 2004 - 21:24:59 MSD