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

UptoLike

ВУЗ: 

ТГУ | Томск

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

Рубрика: 

В силу теоремы Клини о рекурсии существует программа p такая, что F(p) = p, т. е.
существует программа, печатающая (на любом входе) свой собственный текст.
Написать куин – хорошая и популярная задача для любителей программирования.
Неформальную инструкцию на русском языке можно представить следующим образом:
напечатать два раза, второй раз в кавычках
, такой текст:
«напечатать два раза, второй раз в кавычках, такой текст:»
В наиболее чистом виде явление самовоспроизведения можно выразить в лямбда–
исчислении. Известный комбинатор (λx. x x) (λx. x x) редуцируется к самому себе
(λx. x x) (λx. x x) → (λx. x x) (λx. x x).
Этому комбинатору соответствует в Лиспе форма – ламбда-выражение,
примененное к такому же ламбда-выражению с формой quote, т. е. это лямбда-вызов:
((lambda (x) (list x (list ‘quote x))) ‘(lambda (x) (list x (list ‘quote x))))
Форма является одновременно автоаппликативной! Она содержит изображение самой
себя, но не целиком, поскольку такое изображение было бы бесконечно длинным.
Изображение получается ограниченным благодаря механизму блокировки и ламбда-
механизму, а также благодаря автоаппликации.
Достаточно просто написать куин на языке Haskell (автор Jon Fairbairn:
[email protected]):
main = putStr (quine q)
quine s = s ++ show s
q = "main = putStr (quine q)\nquine s = s ++ show s\nq = "
Таким образом, куин на языке Haskell полностью повторяет неформальную инструкцию
на русском языке.
Написание куинов на процедурных языках требует некоторых хитростей. Вот
пример на Паскале:
var a:array[1..7] of string;
i:integer;
begin
a[1]:='var a:array[1..7] of string;';
a[2]:=' i:integer;';
a[3]:='begin';
a[4]:='for i:=1 to 3 do writeln(a[i]);';
a[5]:='for i:=1 to 7 do writeln(#97#91,i,#93#58#61#39,a[i],#39#59);';
a[6]:='for i:=4 to 7 do writeln(a[i]);';
a[7]:='end.';
for i:=1 to 3 do writeln(a[i]);
for i:=1 to 7 do writeln(#97#91,i,#93#58#61#39,a[i],#39#59);
for i:=4 to 7 do writeln(a[i]);
end.
Чтобы понять эту программу полезно иметь в виду соответствие между символами
и кодами:
a
[ ] : = ; '
97 91 93 58 61 59 39

Страницы