Теория алгоритмов. Зюзысов В.М. - 20 стр.

UptoLike

ВУЗ: 

ТГУ | Томск

Составители: 

Рубрика: 

Предложенный текст куина на Паскале имеет существенный недостаток: он
использует значения кодов ASCII – но коды не являются частью самого языка Паскаль.
Следующий куин исправляет этот недостаток (автор Dan Hoey:
[email protected]):
program s;const bbb='program s;const bbb';a='a';b='b';bb=');writeln(';
aa='''';ab='=''';ba=''';';
aaa='begin writeln(bbb,ab,bbb,ba,a,ab,a,ba,b,ab,b,ba,b,b,ab,bb,ba';
aba='a,a,ab,aa,aa,ba,a,b,ab,ab,aa,ba,b,a,ab,aa,ba,ba';
abb='a,a,a,ab,aaa,ba);writeln(a,b,a,ab,aba,ba);writeln(a,b,b,ab,abb,ba';
baa='b,a,a,ab,baa,ba);writeln(b,a,b,ab,bab,ba);writeln(aaa,bb';
bab='aba,bb);writeln(abb);writeln(bb,baa);writeln(bb,bab)end.';
begin writeln(bbb,ab,bbb,ba,a,ab,a,ba,b,ab,b,ba,b,b,ab,bb,ba);writeln(
a,a,ab,aa,aa,ba,a,b,ab,ab,aa,ba,b,a,ab,aa,ba,ba);writeln(
a,a,a,ab,aaa,ba);writeln(a,b,a,ab,aba,ba);writeln(a,b,b,ab,abb,ba
);writeln(b,a,a,ab,baa,ba);writeln(b,a,b,ab,bab,ba);writeln(aaa,bb
);writeln(aba,bb);writeln(abb);writeln(bb,baa);writeln(bb,bab)end.
Как видим, вопреки общепринятому мнению, куин на процедурном языке не обязан
содержать итерацию или рекурсию.
Множество куинов на различных языках можно найти на сайте:
Куины:
www.nyx.net/~gthompso/quine.htm
2.4 Некоторые алгоритмически неразрешимые проблемы
... Найти задачу – не меньшая радость,
чем отыскать решение.
Томас де Куинси
– Это же проблема Бен Бецалеля. Калиостро
же доказал, что она не имеет решения... Как
же искать решения, когда его нет?
Бессмыслица какая-то...
– Бессмыслица – искать решение, если оно и
так есть. Речь идет о том, как поступать
с
задачей, которая решения не имеет.
А. и Б. Стругацкие.
Понедельник начинается в субботу
Решение вопроса о том, обладают ли натуральные числа данным свойством,
является часто встречающейся задачей математики. Поскольку свойства чисел можно
выразить с помощью подходящего предиката, то решение задачи сводится к выяснению
того, является ли данный предикат разрешимым
или нет (т.е. существует ли алгоритм,
который позволил бы распознать, является ли предикат истинным или ложным; см. раздел
5.1). Задачи с произвольными универсумами во многих случаях можно
переформулировать в виде задач с натуральными числами, если использовать подходящее
кодирование.
В контексте разрешимости предикаты часто называются проблемами.
Имея точное определение вычислимости, удалось
доказать, что некоторые
проблемы неразрешимы.
Теорема 8 (теорема Черча о неразрешимости логики предикатов. (см. раздел 4).
Не существует алгоритма, который для любой формулы логики предикатов
устанавливает, общезначима она или нет.
Теорема 9. Проблема остановки неразрешима. Не существует никакого общего
алгоритма, позволяющего установить, остановится ли некоторая конкретная программа

Страницы