Taka bardzo duża funkcja

Wiele lat temu, gdy jeszcze nikt nie wymyślił ruchu wolnego oprogramowania, ludzie także programowali dla przyjemności. Komputery osobiste, ze względu na cenę, były raczej niedostępne. Amatorom pozostawały kalkulatory, mające zwykle kilkadziesiąt do kilkuset kroków programowania. Wydawało się, że za ich pomocą można wszystko obliczyć. I rzeczywiście, bardzo szybko napisano wyrafinowane programy, łącznie z nawigacją statku kosmicznego. Ten ostatni program był tak długi, że wymagał kilku kart magnetycznych, które astronauci kolejno wprowadzali do pamięci.

Nie miałem powodu, aby kierować za pomocą komputera żadnym pojazdem, ale też chciałem napisać jakiś program, który mógłbym opublikować i zyskać nieśmiertelną sławę. Publikowanie oznaczało wtedy wydrukowanie listy poleceń programu i wysłanie do pisma, które kopiowało wydruk ręcznie, co często prowadziło do późniejszych sprostowań. Dlatego też postanowiłem, że moje arcydzieło będzie krótkie. W domowej bibliotece ojca-matematyka udało mi się znaleźć definicję funkcji Ackermana. Wyglądała na prostą, tym bardziej że wykorzystywała rekurencję. Po kilku dniach myślenia wykombinowałem, jak za pomocą stosu oraz rejestrów pamięci mogę zrobić tę rekurencję. Mój HP 41CV miał około 2 tysięcy kroków programowych, które można było w tzw. bankach zamieniać na pamięć (von Neumann się kłania). Pobawiłem się moim kodem i tak go zoptymalizowałem, że miał ledwie kilkadziesiąt linijek (odwrotna polska notacja RPN pozwalała na bardzo efektywne kody, bliższe assemblerowi). Całą resztę pamięci przeznaczyłem na rejestry, których zostało ponad trzysta. Byłem bardzo dumny z mojej pracy, tym bardziej że dla niskich parametrów wyniki obliczeń zgadzały się z podanymi w podręczniku. Pełen optymizmu, przed snem zapuściłem program obliczający funkcję A(4,3). Gdy obudziłem się rano, program dalej coś liczył. Zostawiłem go i poszedłem do pracy. Kalkulator był oczywiście podłączony do zasilacza, bo bateria starczała ledwie na parę godzin pracy. Z dzisiejszej perspektywy procesor kalkulatora wydawałby się bardzo powolny (340 kHz), nawet w porównaniu z telefonem komórkowym, ale ćwierć wieku temu było to poważne urządzenie liczące. Nic dziwnego, że gdy wróciłem po południu do domu i kalkulator dalej liczył, to zmartwiłem się. Czyżbym zapętlił program? Poczekałem jeszcze jedną noc. Program dalej liczył. Wyłączyłem go i zapuściłem raz jeszcze. Z tym samym efektem po dwóch dniach.

W czasach internetu od ręki wyszukałbym informację, że funkcja Ackermanna, którą próbowałem obliczyć, nie da się łatwo zapisać jako liczba dziesiętna. Ba, nie wiadomo, czy taka duża liczba naturalna w ogóle ma jakiś sens, bo jest ona większa od liczby wszystkich obiektów we wszechświecie, zliczając cząstki elementarne oraz ich składowe jako odrębne twory. Wielkość liczby, którą usiłowałem obliczyć, spowodowała utratę przeze mnie wiary w matematykę jako naukę stosowaną. Ale samą funkcję zapamiętałem bardzo dobrze. Na tyle, że już dwa razy (w latach 1998 oraz 1999) odwoływałem się do niej w felietonach. A przecież gdybym lepiej studiował literaturę przedmiotu, to do programu, który miał uczynić mnie nieśmiertelnym, wybrałbym jakąś inną funkcję. Na przykład tzw. 91, zaproponowaną przez McCarthy’ego. Zamiast rosnąć jak na drożdżach, zwija ona do 91 wszystkie liczby mniejsze niż 102, zaś większe lub równe zmniejsza o 10. Zastosowana rekurencyjnie w stosunku do każdej liczby prowadzi zawsze do tego samego wyniku. Właściwie zamiast kodować algorytm, można ją zapisać w jednej linijce: "po wprowadzeniu dowolnej liczby wyświetl 91". Byłby to zapewne najkrótszy program. Ale taki mądry to ja jestem dopiero dzisiaj. A może tylko bardziej leniwy?!

W celu komercyjnej reprodukcji treści Computerworld należy zakupić licencję. Skontaktuj się z naszym partnerem, YGS Group, pod adresem [email protected]

TOP 200