8299308029

Na matematycznych mapach komputery są znacznie prostsze i bardziej idealne niż w rzeczywistości. Najczęściej mają nieograniczoną pamięć, dysponują nieograniczonym czasem na wykonanie obliczeń, operacje arytmetyczne na dowolnie dużych liczbach wykonują bezbłędnie i w czasie jednostkowym, itp. Ściśle biorąc, to wszystko jest nieprawda, ale chwilowe zapominanie np. o tym, że komputer wykonuje niedokładnie operacje na liczbach rzeczywistych, często pozwala nam się skupić na problemach bardziej istotnych.

Matematyczne podstawy informatyki to obecnie dziedzina bardzo szeroka i zróżnicowana; trudno o specjalistę, który orientowałby się w jej całości. Nie sposób jej zaliczyć do jakiegoś konkretnego działu matematyki, bo czerpie po trochu ze wszystkiego, od logiki formalnej i teorii kategorii, przez teorię mnogości, algebrę i topologię, do działów analitycznych. Ponadto informatyka wytworzyła własne teorie, których motywacja jest komputerowa, ale metodą badawczą jest dowodzenie twierdzeń z pełnym matematycznym rygoryzmem.

W tym krótkim opracowaniu nie ma miejsca na omówienie, choćby szkicowe, wszystkich obszarów zainteresowań matematyki komputerowej. Również w dziedzinach wspomnianych zieją wielkie nieomówione luki. Mam nadzieję jednak, że przekona ono czytelnika, że info-matyka potrzebuje rozważań matematycznych; jak też, że dostarcza matematyce problemów badawczych.

W kolejnych rozdziałach omawiam szkicowo problemy matematycznych korzeni informatyki. W ostatnim rozdz. 1.8 tylko już wymieniam to, co nie znalazło miejsca we wcześniejszym tekście.

Większość pozycji w cytowanej bibliografii stanowią nieliczne podręczniki, w miarę możności dostępne na polskim rynku księgarskim lub przynajmniej w czytelniach¹. Uznałem za niewłaściwe zasypywanie czytelnika stosem literatury, po którą i tak nie sięgnie. Artykuły z czasopism naukowych pojawiają się tylko w ostateczności. Ten wybór podyktowany został względami na potrzeby osób, które chciałyby zapoznać się z matematycznymi korzeniami informatyki, ale nie planują zostać specjalistami w tej dziedzinie.

Omówienia poruszanych tu tematów stosunkowo łatwo można znaleźć w internecie, choćby w Wikipedii. Jednak do uzyskanych stamtąd informacji należy podchodzić ostrożnie i starannie oddzielać ziarno od plew.

1.2 Matematyczne modele obliczeń

Teoretycznego badania własności obliczeń dokonuje się na modelach matematycznych. Stanowią one uproszczone idealizacje prawdziwych komputerów, oczyszczone ze szczegółów odwracających uwagę.

W tym rozdziale zostaną omówione dwa spośród wielu rozważanych modeli:

•    automaty skończone — bardzo proste z ograniczonymi możliwościami, oraz

•    maszyny Turinga — model obejmujący „wszystkie”² własności obliczeń.

Innego rodzaju modelem obliczeń, związanym z powyższymi, ale już niebędącym ideali-zacją urządzenia liczącego, jest

3

1

   Sprawdziłem ich obecność w bibliotece Uniwersytetu Gdańskiego. Mam nadzieję, że skoro tam są, to w innych bibliotekach uniwersyteckich też będą.

2

   Matematyk nie może upierać się, że modelowane są naprawdę wszystkie własności fragmentu rzeczywistości; stąd cudzysłów. Niżej (podrozdz. 1.2.2.4) zostanie wyjaśnione, w jakim sensie została użyta ta przenośnia.