Liczby Całkowite i Estymaty

Co to jest: a^2 + b^2 = c^2

Twierdzenie Pitagorasa

Dobrze. Czym jeszcze to jest?

Równaniem z trzema niewiadomymi.

Znasz jakieś rozwiązania tego równania?

Jasne. (3,4,5) i (5,12,13).

---

---

Dobrze. To są często spotykane trójki pitagorejskie. Znasz jakieś inne?

Cóż, Google jest moim przyjacielem, zobaczmy. (wpisuje) Wygląda na to, iż (7,24,25) i (9,40, 41) spełniają to równanie.

Zauważyłeś, iż te rozwiązania, które podałeś zawieraja tylko liczby całkowite?

Ooo, no tak. Przypuszczam, iż jest całe mnóstwo niecałkowitoliczbowych rozwiązań.

Słyszałeś o Diofantosie?

Czy to nazwisko jakiegoś Greka?

Tak, Diofantos zainteresowany był równaniami, które mają rozwiązania złożone z liczb całkowitych. Nazywamy takie równania równaniami diofantycznymi.

Więc a^2 + b^2 = c^2 jest równaniem diofantycznym?

Tak. I jest też wiele innych. Na przykład: a^3 + b^3 = c^3

Ok, spoko. I jakie są przykładowe rozwiązania?

Nie ma żadnych.

Naprawdę? Żadnych?

Tak. Żadnych. To zostało udowodnione. W rzeczywistości zostało udowodnione, iż każde równanie a^n + b^n = c^n nie ma całkowitoliczbowych rozwiązań dla n > 2. To jest znane jako Wielkie Twierdzenie Fermata

Hmm. To mogłoby być całkiem interesujące, ale dlaczego mam się tym przejmować w ogóle?

Co to jest komputer cyfrowy?

Co masz na myśli? Ta rzecz na której Ty i ja rozmawiamy jest komputerem cyfrowym.

Tak, ale co dokładnie robi komputer cyfrowy?

Yyy. Oblicza cyfrowo?

Dokładnie! I słowo cyfrowy oznacza ... ?

Hmm. Z użyciem cyfr?

Własnie! I czy liczba tych cyfr jest skończona?

Oczywiście, choć bardzo, bardzo duża w dzisiejszych czasach.

... i skończona liczba cyfr to...?

Ooo, myślę, iż wiem, do czego zmierzasz. Skończona liczba cyfr jest liczbą całkowitą.

Tak. Komputer cyfrowy to komputer, który oblicza przy użyciu liczb całkowitych. Przy użyciu tylko liczb całkowitych, niczego innego.

No cóż, chwileczkę. A co z liczbami zmiennoprzecinkowymi i liczbami wymiernymi.

Są reprezentowane w komputerze przez liczby całkowite. Komputer radzi sobie z liczbami całkowitymi - tylko z liczbami całkowitymi.

OK. Dobra. Liczby całkowite. Ale co to ma wspólnego z równaniami diofantycznymi?

Jakie są wejścia programu komputerowego?

Jest wiele różnych typów. Znaki z klawiatury, ruchy myszki, kliknięcia myszki, pakiety internetowe. Do wyboru, do koloru.

One są pod spodem liczbami całkowitymi, prawda?

Hmm. No tak. Wydaję mi się, iż są. OK, czyli każde wejście do programu komputerowego to liczby całkowite.

A co z wyjściami?

No cóż, tak, piksele, znaki, pakiety sieciowe. One wszystkie też są złożone z liczb całkowitych.

Więc komuter cyfrowy pobiera liczby całkowite i zwraca liczby całkowite.

Prawda. Masz rację. To wszystko liczby całkowite.

Program komputera cyfrowego, zatem, reprezentuje równanie diofantyczne.

Czekaj. Co?

Liczby całkowite na wejściu. Liczby całkowite na wyjściu.

Ok. Pewnie. Ale to całkiem duże, skomplikowane równanie diofantyczne.

Właściwie, specyfikacja programu jest równaniem. Program znajduje rozwiązanie tego równania.

Tak, tak, OK. To prawda. Specyfikacja programu jest jednym wielkim równaniem diofantycznym z tryliolem niewiadomych i program spełnia tę specyfikację znajdując rozwiązanie tego ogromniastego równania. Czy ta wiedza jest do czegoś potrzebna?

Kto to jest David Hilbert?

Masz na myśli tego gościa, który zaprojektował tę śmieszną rekurencyjną krzywą, która wyglada jak siatka na owady?

(Yhy) To było jedno z jego osiągnięć, tak. On także pomógł Einsteinowi z Ogólną Teorią Względności. Był wspaniałym matematykiem.

I zgaduję, iż zrobił coś w temacie równań diofantycznych

W rzeczy samej on robił wiele, wiele rzeczy. Pośród nich było słynne pytanie. Pytanie o "Entscheidung" - rozstrzygalność.

Co on chciał rozstrzygnąć?

Pamiętasz Wielkie Twierdzenie Fermata?

Masz na myśli to równanie, które nie ma rozwiązań. a^n + b^n = c^n gdzie n > 2?

Tak, właśnie to. Przez długi czas nie było dowodu, iż przy n = 2 równanie ma jedyne rozwiązanie. Jak możesz obalić przypuszczenie, o ile wydaje Ci się ono nieprawdą?

Mógłbym napisać program, który znajduje kontrprzykłady. Na przykład dla n=999999999 to mogłoby zadziałać.

Dobra. I gdybyś znalazł takie rozwiązanie to obaliłbyś Twierdzenie Fermata. Ale jak długo zajęłoby Ci DOWIEDZENIE tego twierdzenia przy użyciu tej metody?

Program wykonywałby się w nieskończoność. Nie mógłbym dowieść twierdzenia w ten sposób.

Dokładnie. To, czego Hilbert chciał, to skończony algorytm do sprawdzenia czy rozwiązanie istnieje, czy nie. Chciał sposobu "decydowania" czy poszukiwania, takie, jak Ty zaproponowałeś byłyby praktyczne.

Czekaj, zaraz. Co? Nie szukał rozwiązań. Szukał możliwości dowiedzenia się czy byłyby rozwiązania?

Tak. Chciał skończonego algorytmu, który powiedziałby, czy dane równanie diofantyczne ma rozwiązania czy nie. Ten algorytm nie dostarczałby rozwiązań; dostarczałby tylko rozstrzygnięcie.

To dlatego nazwał to "rozstrzygalnością"?

Entscheidung. Tak.

Gesundheight!

Harumph! A teraz. Kto Twoim zdaniem rozwiązał problem rozstrzygalności?

Sądzę, iż zaraz mi powiesz.

Dwoje ludzi, o których już słyszałeś. Dwoje wielkich ojców współczesnej informatyki. Alonzo Church i Alan Turing.

Church! To ten gość, który wymyślił programowanie funkcyjne, tak?

W pewnym sensie tak.

I Turing! Wygrał II Wojnę Światową, prawda?

No, na pewno się dołożył. Oni oboje udowodnili, używając zupełnie innych sposobów, iż nie istnieje ogólne i skończone rozwiązanie dla rozstrzygalności.

To musiało zawieść Hilberta.

Być może. Ale nie o to chodzi.

OK, no to o co chodzi?

Kiedy dają Ci specyfikację programu, to jest równania diofantycznego, to o co zwykle proszą Cię na początku?

O estymatę oczywiście. Goście chcą wiedzieć jak długo potrwa napisanie programu.

I jeszcze raz, czym jest program w świetle równania diofantycznego?

Program jest ... rozwiązaniem ... dla ... AAA!

(uśmiech) Wydaje mi się, iż zaczynasz rozumieć.

Taaa, że, oni proszą mnie abym ROZSTRZYGNĄŁ. Estymata jest rozstrzygnięciem.

I czy istnieje skończona metoda znalezienia rozstrzygnięcia w każdym przypadku?

Nie! O KURKA, to zabawne.

No właśnie. Fundamentalne podstawy informatyki dowodzą, iż nie istnieje skończony mechanizm rozstrzygania czy program może być kiedykolwiek napisany. Fundamenty informatyki oparte są na dowodzie, iż estymaty nie są gwarantowane.

No tak, ale przez cały czas MOŻEMY estymować.

Tak, możemy. Ponieważ większość specyfikacji jest estymowalna.

A więc to była tylko mała matematyczna rozrywka bez żadnego użytecznego zastosowania.

Można tak powiedzieć. Ale podobało mi się to. Poza tym, to przepysznie ironiczne, iż to właśnie dowód o NIEESTYMOWALNOŚCI stoi u podstaw dzisiejszej informatyki.

---

---