Pomysł, żeby w filozofii matematyki i filozofii informatyki dyskutować o nieistnieniu liczb jest inspirujący. Pojawił się on we wpisie 25.XII.2018 pt. „O nieistnieniu liczb w informatyce” podpisanym „Jarek”: http://marciszewski.eu/?p=10032
Myślowym punktem wyjścia jest dla Jarka słynne zdanie Leopolda Kroneckera (1823-1891): Die ganzen Zahlen hat der liebe Gott gemacht, alles andere ist Menschenwerk (Miły Bóg stworzył liczby całkowite, wszystkie inne są dziełem ludzkim). Tę sentencję przytacza Jarek, zmieniając tylko zwrot „liczby całkowite” na „liczby naturalne”, z pożytkiem dla obecnych rozważań. Skupią się one bowiem na PA (Arytmetyce Peano), a więc na liczbach naturalnych (czyli całkowitych dodatnich z uwzględnieniem zera).
Z liczbami naturalnymi związany jest też fakt, że właśnie zaistniały Nowy Rok numerowany jest liczbą 2019, a taka numeracja bierze się z naszej potrzeby widzenia świata jako struktury dyskretnej. Kapitalnie ujął to Boy.
By uniknąć ambarasu
wzięto rok za miarę czasu,
dzieląc go bardzo wygodnie
ma miesiące i tygodnie.
Na pomysł udyskretnienia czasu wpadli ludzie. A co ma do tego dobry Bóg przywołany przez Kroneckera? Istotnie się do tego przyczynił, każąc ziemi okrążać bez przerwy słońce, co podsunęło ludziom dowcipny pomysł, żeby z jednego takiego okrążenia uczynić miarę czasu. A dalej poszło łatwo, bo za sprawą tegoż Astronomicznego Wynalazcy mamy noce i dnie, a dzięki Euklidesowi, Peano etc. mamy arytmetykę z dzieleniem (czego nie ma np.arytmetyka Presburgera), tak więc podzielono liczbę dni roku, żeby wyszły zgrabnie „miesiące i tygodnie”. Za dzielenie płacimy nierozstrzygalnością arytmetyki (czym nie musiał martwić się Presburger), ale to drobiazg w porównaniu z wygodą poruszania się w tak uładzonym czasie.
Dzięki refleksji nad kalendarzem i astronomią, możemy nadać sentencji Kroneckera uchwytne znaczenie: liczby naturalne istnieją przynajmniej w ten sposób, że są niezbędne do opisu świata, np. do mierzenia upływu czasu. Nie zmusza to nas do poglądu że istnieją w jeszcze innym sensie, np. na sposób platoński. Mogą krytycy Platona ubolewać nad fantastyką wiary w istnienie liczb, ale to nie zmieni faktu, że będziemy się nimi posługiwać, jak gdyby one w najlepsze istniały. Pragmatyście to wystarczy.
Zauważmy jednak, że segmentowanie czasu za pomocą liczb naturalnych jest pomysłem ludzkim, a tak naprawdę, to owe segmenty składają się z punktów. Wprawdzie ignoruje to sekundnik zegara (według niego sekunda jest odcinkiem czasu), ale nie wszystko w przyrodzie pozwala ignorować punktowość. Nie pozwala m.in. mechanika, gdzie przyspieszenie jest pochodną prędkości względem czasu rozumianego jako zbiór punktów, a te są reprezentowane arytmetycznie przez liczby rzeczywiste. Mamy więc dobry powód do zachowywania się w sposób analogiczny jak w przypadku liczb naturalnych. Według pragmatysty usprawiedliwia to praktykę stosowania kwantyfikatora egzystencjalnego do zmiennych, które się odnoszą do liczb rzeczywistych. Jeśli nominalista się z tym nie zgadza, to niech składa skargę do Trybunału Rzeczywistości.
*** 9 stycznia 2019 ***
W miejscu do gwiazdek przerwałem 1-go stycznia pisanie, zapowiadając, że ciąg dalszy nastąpi. Żeby to zrealizować, uznałem, że trzeba w poszukiwaniu argumentów staranniej niż dotąd wniknąć w opublikowane wpisy i komentarze. Zaczynam od wpisu rejestrującego wymianę zdań między SP i Harrym, która zainicjowała dalszą dyskusję. Otwiera ją głos Pawła Stacewicza.
[PS] „W mojej opinii, zarówno pojęcie liczby, jak i pokrewne mu pojęcie kodowania liczbowego (tj. zapisywania danych przetwarzanych przez komputery za pomocą liczb), jest w metodologii i filozofii informatyki niezbędne.”
Zdziwiło mnie trochę zastrzeżenie „w mojej opinii” dotyczące przecież poglądu wielce umiarkowanego („niezbędne”, a nie np. „fundamentalne”), którego oczywistość leży jak na dłoni. Skąd miałaby się brać różnica opinii? A jednak… Zabrał głos Harry, wyznając, że owa opinia „nie bardzo go przekonuje”. Posłuchajmy.
[H] „Ten sam problem pojawia się bowiem na poziomie metateoretycznym: czy na pewno reprezentacja matematyczna jest niezbędna w informatyce teoretycznej? Jeśli tak, to dlaczego?”
Mimo użycia słowa „bowiem”, passus ten , złożony tylko z pytań, nie daje jeszcze
uzasadnienia. Pojawia się ono po replice PS-a, która przywołuje takie oczywistości, jak nieodzowność w informatyce koncepcji maszyny Turinga, także nieodzowność arytmetycznego pojęcia funkcji rekurencyjnej, a także rola nieskończonych reprezentacji liczb nieobliczalnych. Harry odpowiada.
[H] „Nie do końca mnie zrozumiałeś. Chodzi mi o matematyczność w wąskim sensie, związanym z teorią liczb. W tym sensie maszyny Turinga i algorytmy nie są obiektami matematycznymi. Są właśnie obiektami typowo informatycznymi, w opisie których nie posługujemy się (lub ostrożniej: nie musimy posługiwać się) 'językiem liczb’.”
Nerw argumentacji jest w ostatnim zdaniu. Zdaje się zeń wynikać, że możliwy jest opis maszyny Turinga, w którym nie wystąpiłyby ani razu słowa „liczba” i funkcja”, ani jakieś konkretne liczby (a jest ich de facto mnóstwo, np. numery kodowe poszczególnych maszyn Turinga, nieskończone ciągi zer i jedynek w argumencie przekątniowym etc.). Takie dokonanie — pokazanie zbędności arytmetyki w informatyce — byłoby rewelacją na miarę osiągnięć samego Turinga.
Powyższa wypowiedź tym bardziej godna jest uwagi, że powołuje się na pewien wynik, który Harry zdaje się uważać za sukces porównywalny z tym, jakim byłoby owo sparafrazowanie wyników Turinga bez używania słowa „liczba” i nazw konkretnych liczb. Tym przywołanym przezeń wynikiem jest A.Grzegorczyka dowód nierozstrzygalności zainicjowanej przez Tarskiego teorii konkatenacji, mianowicie dowód, który się obywa bez aparatu pojęciowego arytmetyki („Undecidability without arithmetization” w „Studia Logica”, 1(79):163?230, 2005).
Ten punkt argumentacji stanowi istotny wkład do dyskusji. Wskazuje bowiem pewien wzorzec pomocny w szukaniu drogi, na jakiej należałoby bronić poglądu, że informatyka nie potrzebuje pojęcia liczby i, w ogólności, arytmetyki. Mianowicie, należałoby zastosować teorię konkatenacji, lub jakąś inną też nie posługującą się pojęciem liczby, żeby powtórzyć na innej drodze wynik Turinga, to jest: dać definicję funkcji obliczalnej i wykazać istnienie liczb nieobliczalnych, ale bez mówienia o liczbach.
Nim ktoś się podejmie takiego zadania, niechby jako zadatek dał krótką zapowiedź tego, jak zamierza oddać tytuł przełomowego studium Turinga (1936) „ON COMPUTABLE NUMBERS, WITH AN APPLICATION TO THE ENTSCHEIDUNGSPROBLEM” bez użycia słowa „number”.
Dzięki powyższej sugestii, mogę z czystym sumieniem zaprzestać udziału w tej żywej dyskusji (3 wpisy i 43 komentarze). To znaczy, mogę z pozycji aktywnej przejść do „spocznij”. I spokojnie czekać, aż Harry lub inny obrońca tezy o zbędności pojęcia liczby w informatyce opublikuje pracę, która (powtarzam): dostarczy definicji funkcji obliczalnej oraz dowodu istnienia liczb nieobliczalnych, bez posługiwania się aparatem pojęciowym arytmetyki.
O ile to się komuś uda, wrócę do obecnej dyskusji. Ale już po to tylko, żeby samokrytycznie wyznać, że błądziłem, uważając takie przedsięwzięcie za nierealne.
Przywołanie czasu i jego upływu daje znakomitą okazję do zilustrowania kolejnymi przykładami rozważań z poprzedniego wpisu.
Czas jest ciągły (tak zakładam, choć w fizyce nie ma co do tego absolutnej zgody), a kalendarz posługuje się rosnącymi liczbami naturalnymi. Za początek tego liczenia uznano Wielkie Wydarzenie, które dopiero co świętowaliśmy. Tak oto zrealizowano pierwszy i trzeci aksjomat Peano mówiące o początku. Potem korzystamy z aksjomatu drugiego, który zapewnia nas, że kolejnych liczb do numerowania lat nigdy nie zabraknie.
Przez wieki, od samego początku ery, tak do tego podchodziliśmy. Ale potem przyszli informatycy ze swoimi maszynami cyfrowymi i innym podejściem do liczb. Równo 19 lat temu świat z obawą patrzył na to, co stanie się za kilka dni. Niektórzy wręcz uważali, że nastąpi koniec świata. Uczciwie trzeba powiedzieć, że nie po raz pierwszy. Tysiąc lat wcześniej, za pontyfikatu Sylwestra II, też wieszczono koniec świata, ale jego przyczyną miała być magia liczby tysiąc. Za naszych czasów magii już nie było, był problem roku 2000 (Y2K).
Problem ten wynika wprost z nieistnienia liczb naturalnych (nieskończony zbiór o mocy ℵ0) w informatyce. Programiści, oszczędzając cenne zasoby pamięci komputerów, przeważnie zapisywali dwie ostatnie cyfry liczby lat w jednej zmiennej typu integer o najmniejszej długości, czyli w jednym bajcie. Pół biedy, gdyby wszyscy oni chcieli dalej posługiwać się arytmetyką i dodali „swoją” liczbę do liczby 1900 – wtedy kłopoty udało by się odroczyć do roku 2028 lub 2156. Na ogół jednak używali konkatenacji napisu „19” i reprezentacji dziesiętnej zmiennej z numerem roku. Dawało to napis „19100”, „1910” albo „190”. To, co najczęściej wróżyli dziennikarze, czyli zwykłe „przekręcenie się licznika” i rok 1900 występowało chyba najrzadziej.
O problemie roku 2000 zdążyliśmy już zapomnieć, niektórzy uważają, że to jednostkowy przypadek spowodowany niedostatkiem pamięci starych komputerów. Ale tak nie jest. Istnieje też „problem roku 2038” – systemy uniksowe odliczają czas w sekundach od 1 stycznia 1970 roku, za kilkanaście lat minie tych sekund przeszło dwa miliardy, a dokładnie 231 – tyle, ile może pomieścić zmienna całkowita. Gdyby nic z tym nie robić, to po 19 stycznia 2038, godzina 03:14:07 nastąpi 13 grudnia 1901 roku, godzina 21:45:52. Ale robi się – zmienne 32-bitowe zamieniane są w kodach źródłowych programów na zmienne 64-bitowe. To odracza nam wystąpienie problemu na jakieś 300 miliardów lat.
Informatykom-praktykom to wystarcza, nikt nie zamierza żyć 300 miliardów lat. Za to teoretycy dobrze wiedzą, że liczny naturalne w wymiarze materialnym (fizycznym) nie istnieją. Hotelu Hilberta nie udało się zbudować, na komputer Hilberta też się nie zanosi.
Nie umiem podzielić optymizmu Autora, jakim został zarażony przez Boya, a dotyczącym „zgrabnego i wygodnego” podziału roku na miesiące. Z tym numerycznym problemem zmagano się przez całe wieki. Rok nie dzieli się na całkowitą liczbę dni, stosunek tych dwu okresów opisuje liczba rzeczywista. W pewnym sensie nieobliczalna – na skutek utraty energii w ruchach pływowych Ziemi doba wciąż się wydłuża, a z jeszcze innych powodów wydłuża się rok. Proporcja się zmienia i nie nadążamy rachować. Pierwszym przybliżeniem może być 365 dni w roku – ale niedoskonałość takich rachunków da się zaobserwować nawet w czasie życia jednego pokolenia, kalendarz się śpieszy. Długo wytrwał kalendarz Juliański z dodatkowym dniem co cztery lata, lecz ten dla odmiany się spóźnia. Kalendarz Gregoriański, zręcznie ujmując część lat przestępnych, jest lepiej dopasowany. Ale wiemy, że dobry kalendarz idealnie opisujący boskie proporcje po prostu nie istnieje.
Jarek
PS:
Straszono nas też nadejściem końca świata w dniu 12 grudnia 2012. Wtedy to miał skończyć się kalendarz wymyślony przez Majów. Majowie, inaczej niż my, nie uznali za stosowne użycia liczb naturalnych i arytmetyki Peano. Ich kalendarz, zupełnie jak typ „integer” w komputerach, zna tylko liczby o ograniczonej długości. Oraz powtarzające się (lecz już nienumerowane) cykle. Dzięki temu ostatniemu żyjemy – wraz z otwarciem nowego, skończył się stary cykl, a nie cały świat.
Nim ktoś się podejmie takiego zadania, niechby jako zadatek dał krótką zapowiedź tego, jak zamierza oddać tytuł przełomowego studium Turinga (1936) „ON COMPUTABLE NUMBERS, WITH AN APPLICATION TO THE ENTSCHEIDUNGSPROBLEM” bez użycia słowa „number”.
A czy w roli zapowiedzi może wystąpić to, co Turing napisał w drugim zdaniu przytoczonego studium, zapowiadając o czym ono będzie? Cytuję:
„So fort” jest bardzo pojemne, mieści się w nim może nawet więcej, niż Turing miał na myśli, a lektura całości wywodu autora w pełni potwierdza „ostensibility”.
Dalej Turing pisze tak:
I trzeba przyznać, że tej deklaracji się trzyma — dalej w pracy używa wyłącznie (kilkanaście razy) frazy „computable sequences”. Jeśli pojawia się „computable numbers”, to dla pokazania, że jest to matematyczna konsekwencja wynikająca z istnienia wcześniej opisanego bytu informatycznego (CS).
* * *
Nie jestem rzecz jasna Wrogiem Liczb Jako Takich. Nie pretenduję też do roli odkrywcy — wszystko, co do tej pory napisałem w trakcie długiej dyskusji, zgadza się całkowicie z moim odczytaniem pracy Turinga. Warto odświeżyć sobie tę lekturę (przynajmniej w części dotyczącej samych maszyn).
No dobrze… Niech będzie że Turing bardziej kierował uwagę czytelnika na kwestię obliczalnych ciągów symboli niż kwestię obliczalności pewnego rodzaju liczb. A także, że powołał do istnienia pewne byty (proto)informatyczne, to znaczy określonego typu abstrakcyjne maszyny i generowane przez nie ciągi symboli (chociaż dla niego były to pewnie byty matematyczne).
Recz jednak w tym, że chcąc badać owe byty, w szczególności zaś możliwości maszyn generujących ciągi symboli, odwoływał się do pojęcia przeliczalności zbiorów, które to pojęcie odnosi w sposób konieczny do pojęć liczby naturalnej i zbioru liczb naturalnych. (Zgodnie z podręcznikiem H. Rasiowej „zbiorami przeliczalnymi nazywamy zbiory skończone lub równoliczne ze zbiorem N wszystkich liczb naturalnych”). A odwoływał się, ponieważ dowodząc istnienia liczb/ciągów nieobliczalnych, a więc wyników nieosiągalnych dla pewnego rodzaju maszyn, przypisywał maszynom liczby naturalne i ustawiał maszyny w nieskończony przeliczalny ciąg.
A zatem: aby uzyskać pewne doniosłe wyniki w zakresie podstaw informatyki, korzystał (i pewnie musiał korzystać) z takich choćby elementarnych operacji na liczbach naturalnych, jak ich porównywanie, porządkowanie i ustawianie w nieskończony ciąg.
Gdy formułowałem powyższe uwagi , przypomniałem sobie swój komentarz sprzed kilkunastu dni do innego wpisu (zwłaszcza jego punkt II): http://marciszewski.eu/?p=9995#comment-14280.
Powtórzę za nim (z pewnymi zmianami) następujące spostrzeżenia, wieńczące punkt II:
1. Analizując swoją konstrukcję w kategoriach liczbowych (wchodzą tu w grę przynajmniej liczby naturalne), Turing dowiódł, że istnieją ciągi cyfr niemożliwe do wygenerowania (w skończonym, choć dowolnie długim czasie) przez maszyny Turinga, i ciągi te odpowiadają pewnym specjalnym liczbom rzeczywistym (nieobliczalnym). W ten sposób odkrył Turing pewne ograniczenia ‘swoich’ maszyn. Ponadto jednak ‘uchylił drzwi’ do definiowania obliczeń innego typu – takich obliczeń, które pozwalałyby mechanizować działania na liczbach nieobliczalnych, być może nawet na wszelkich liczbach rzeczywistych. Ten ostatni warunek spełniają obliczenia analogowe-ciągłe (zdefiniowane po raz pierwszy przez C. Shannona w roku 1941).
2. Zgodnie z ustaleniami Turinga informatyce ograniczonej do analizy technik cyfrowych wystarcza przeliczalny zbiór liczb naturalnych. Informatyce badającej także techniki analogowe zbiór liczb naturalnych nie wystarcza. Odróżniając te techniki od cyfrowych (turingowskich), a także poszukując ich ograniczeń, trzeba powołać się na własności liczb rzeczywistych.
Poszukując zaś ograniczeń technik cyfrowych, trzeba odwołać się do własności liczb naturalnych.
To chyba dobry moment, by przypomnieć co jest przedmiotem tego sporu. Chodzi o (cyt.) „przekonanie, że czymś informatycznie pierwotnym są reprezentacje liczbowe i operacje arytmetyczne”.
Polemika dotyczy pierwotności — z nią całkowicie się nie zgadzam. Chyba wyczerpałem swój zasób głównych argumentów, mógłbym co najwyżej dodać garść pomniejszych. Ale jeśli kogoś do tej pory nie przekonałem, to te mniej zasadnicze dowody nie zrobią tego tym bardziej. Pierwotności nie widzi też sam Turing (z nim również można się nie zgadzać). Jestem w stanie wyobrazić sobie informatykę z liczbami jako fundamentalnymi pojęciami pierwotnymi, ale nie widzę w tym żadnych korzyści. Turing zbudował coś, co prostotą przypomina mi model kopernikański. Inne podejścia są jak kosmos z epicyklami.
Jeśli od tych fundamentów pójdziemy nieco wyżej, do skutków działania maszyny Turinga, to może się okazać, że na tym polu spór jest spowodowany wyłącznie różnym widzeniem tych samych rzeczy. Wtedy o zgodę łatwo. Dla mnie obliczalność, czy badanie liczebności zbiorów, ma z arytmetyką i rachunkami tyle wspólnego, na ile powodują to kwestie lingwistyczne. Gdy latem spadnie gwałtowny deszcz, to porównanie mocy zbioru przechodniów na ulicy z mocą zbioru krzeseł w kawiarniach odbywa się bez liczenia. Albo pozostaną puste krzesła, albo niektórzy przeczekają ulewę stojąc. U Turinga występuje tylko takie liczenie — teoriomnogościowe, przez wskazanie funkcji jednoznacznego przyporządkowania jako dowód równoliczności. Ustawianie w nieskończony ciąg elementów zbioru nie jest dla mnie „elementarną operacją na liczbach naturalnych” — relacja porządku nie ma tu najmniejszego znaczenia. Wystarczy tylko pokazać (co czyni Turing), że taki ciąg da się utworzyć.
Takie uściślenie tematu naszej dyskusji (w postaci pytania „Czy pojęcia arytmetyczne są w informatyce pierwotne?”) wydaje mi się istotne. I zasadniczo przekonują mnie podawane tu argumenty za przeczącą odpowiedzią na to pytanie. Ponieważ nie znam wyników szczegółowych dociekań na ten temat (nie wiem nawet, czy kiedykolwiek były takie prowadzone), nie potrafię definitywnie uznać tego rozwiązania. Jednakże na obecnym etapie dyskusji, zdecydowanie przychylam się do negatywnego rozwiązania tak sformułowanej kwestii.
Skoro nasz problem częściej był tu definiowany jako kwestia zbędności/niezbędności arytmetyki w informatyce, to może warto też pokusić się o zarysowanie jakiegoś związku logicznego między nią a kwestią pierwotności pojęć arytmetycznych w informatyce. Widziałbym to z grubsza tak.
Jeśli pojęcia arytmetyczne są (definicyjnie) wtórne w informatyce, to arytmetyka jest w niej „teoretycznie zbędna” w tym sensie, że można ją w zasadzie rozwijać bez konieczności wprowadzania owych pojęć („w zasadzie” znaczy tu właśnie „teoretycznie”: przyjęcie w praktyce informatycznej takiego ograniczenia prawdopodobnie nie miałoby sensu) . W szczególności jeśli konkatenacja jest w informatyce operacją pierwotną, to zasadniczo można się nią posługiwać zamiast (wtórnych) operacji dodawania i mnożenia liczb.
Być może się mylę, ale implikacja odwrotna chyba nie zachodzi: stąd, że informatyka może być rozwijana bez wyraźnego wprowadzania pojęć arytmetycznych nie wynika, że te pojęcia da się w niej w ogóle wprowadzić. Dlatego teza „Pojęcia arytmetyczne są w informatyce wtórne” wydaje mi się silniejsza od tezy „Arytmetyka jest w informatyce zbędna”. Co może dobrze by o niej świadczyło :)
(1) „Nerw argumentacji [Harry’ego – przyp. Harry’ego] jest w ostatnim zdaniu. Zdaje się zeń wynikać, że możliwy jest opis maszyny Turinga, w którym nie wystąpiłyby ani razu słowa 'liczba’ i 'funkcja’, ani jakieś konkretne liczby […]. Takie dokonanie — pokazanie zbędności arytmetyki w informatyce — byłoby rewelacją na miarę osiągnięć samego Turinga.” (W.M.)
Panie Profesorze, takie dokonanie jest dziełem samego Turinga. A przy okazji też Pawła, który w swoim komentarzu z 20 XII napisał: „Faktycznie, gdy analizujemy pojęcie maszyny Turinga, możemy dojść do wniosku, że pojęcie to nie ma w sobie nic 'liczbowego’: jest ono określone za pomocą bardziej elementarnych pojęć symbolu (z pewnego alfabetu), stanu (dyskretnego), taśmy (wypełnianej symbolami), głowicy (zmieniającej stany i zapisującej/zmazującej symbole) oraz tablicy przejść (wypełnionej rozkazami czysto symbolicznymi).”
(2) „Mogę z pozycji aktywnej przejść do 'spocznij’. I spokojnie czekać, aż Harry lub inny obrońca tezy o zbędności pojęcia liczby w informatyce opublikuje pracę, która (powtarzam): dostarczy definicji funkcji obliczalnej oraz dowodu istnienia liczb nieobliczalnych, bez posługiwania się aparatem pojęciowym arytmetyki.”
Turing wprowadził do literatury definicję funkcji obliczalnej, w której sformułowaniu nie jest wykorzystywany aparat pojęciowy arytmetyki. Definicja pojęcia „funkcji obliczalnej za pomocą maszyny Turinga” nie zawiera terminów arytmetycznych (por. (1)).
Co do zadania wskazania dowodu istnienia liczb nieobliczalnych bez użycia słowa „liczba”, to nie sądzę, by znalazł Pan Profesor chętnego (bo każdy się domyśla, że liczby nieobliczalne są liczbami :)). Jednakże uznając tę niemożliwość, nie posuwamy się ani o cal w tej dyskusji. Problem istnienia liczb nieobliczalnych (rozwiązany pozytywnie przez Turinga) jest bowiem problemem matematycznym, a nie informatycznym.
(3) „Nim ktoś się podejmie takiego zadania, niechby jako zadatek dał krótką zapowiedź tego, jak zamierza oddać tytuł przełomowego studium Turinga (1936) „ON COMPUTABLE NUMBERS, WITH AN APPLICATION TO THE ENTSCHEIDUNGSPROBLEM” bez użycia słowa 'number’”.
Uwzględniając wypowiedzi Turinga, ostatnio przywołane w tej dyskusji, mogę zaproponować taki oto tytuł: „ON COMPUTABLE SEQUENCES, WITH AN APPLICATION TO THE ENTSCHEIDUNGSPROBLEM”.
Wydawszy sobie komendę „W tył zwrot” (po krótkim okresie spoczynku, :)) chciałbym uwypuklić trzy kwestie.
1. Pojęcie liczby.
Czy pojęcie liczby (np. naturalnej) staje się zrozumiałe dopiero wtedy, gdy osadzimy je w teorii arytmetycznej?
Innymi słowy: czy jest tak, (1) że zaczynamy od liczby (jako pojęcia pierwotnego), a dopiero uchwyciwszy i określiwszy je ‘dokładamy’ arytmetykę, cze może tak, że (2) chcąc określić pojęcie liczby, musimy osadzić je w jakiejś aksjomatycznej teorii arytmetycznej.
Być może wykazuję się tu jakąś elementarną niewiedzą, ale trudno… Rozjaśnienie tej kwestii wydaje mi się ważne, bo oryginalne sformułowanie tematu naszej dyskusji odnosi do kategorii liczby, a nie arytmetyki („O teoretycznej (nie)zbędności kategorii liczby…”).
2. Informatyka a matematyka.
Jakie mamy przyjąć kryterium odróżnienia informatyki od matematyki? Czy jest ono ostre?
Sam Turing zagmatwał (a może: dobrze wyczuł) sprawę wprowadzając pojęcie liczby obliczalnej (czegoś matematycznego, tj. liczby, co możemy informatycznie/maszynowo wyznaczać, tj. obliczać).
Harry pisze: „Problem istnienia liczb nieobliczalnych (rozwiązany pozytywnie przez Turinga) jest bowiem problemem matematycznym, a nie informatycznym” – zakładając tym samym jakieś ostre kryterium rozróżnienia informatyki od matematyki.
Dla mnie sprawa nie jest jasna. Patrzę na nią tak, że że matematyczne modele obliczeń – zarówno turingowski, jak i pozaturingowskie (np. analogowy-ciągły) – wchodzą w zakres informatyki teoretycznej.
A przechodząc do oryginalnego tekstu Turinga… Gdy Turing udowodnił istnienie liczb nieobliczalnych, uzyskał rezultat matematyczny, ale był to rezultat, po pierwsze, przynależny do matematycznych podstaw informatyki czyli do informatyki teoretycznej, a po drugie, otwierający możliwość poszukiwania innych niż turingowski modeli obliczeń (np. takich, które opisywałyby maszyny operujące na fizycznych odpowiednikach liczb rzeczywistych). Te poszukiwania zaś znów przynależą, zgodnie z moim punktem widzenia, do informatyki teoretycznej.
Innymi słowy: ja uznaję, że pewne wyniki dotyczące liczb (a nie tylko ciągów symboli) mieszczą się w zakresie badań informatycznych.
Czy te wyniki można sformułować, a wcześniej osiągnąć, w taki sposób, aby w ogóle nie odnosić się do żadnych własności liczb (nawet naturalnych)…? Tutaj, przyznaję, nie mam zdecydowanej odpowiedzi.
3. Równoważność teorii funkcji rekurencyjnych i teorii maszyn Turinga (co do zakresu rozw. problemów)
Czy ta równoważność – a dodatkowo fakt, że uzyskując pewne wyniki w teorii maszyn Turinga posługujemy się własnościami liczb naturalnych – nie świadczy o niezbędności (a przynajmniej: wielkiej przydatności) kategorii liczby w informatyce teoretycznej.
Jarek pisze: „Jestem w stanie wyobrazić sobie informatykę z liczbami jako fundamentalnymi pojęciami pierwotnymi, ale nie widzę w tym żadnych korzyści”. Teoria funkcji rekurencyjnych jest właśnie takim podejściem ufundowanym na pojęciu liczby (naturalnej) i elementarnych operacjach arytmetycznych. Czy informatyka teoretyczna nie odnosi z takiego podejścia żadnych korzyści? Mamy tu przykład podejścia stricte matematycznego, które doprowadza – niejako z góry, zakładając pewne operacje/funkcje matematyczne – do zdefiniowania wyjątkowej klasy funkcji, osiągalnej dla pewnego rodzaju maszyn. Mając jednak „w tle” szerszą klasę możliwych do zdefiniowania funkcji matematycznych, podejście takie pozwala przynajmniej zastanawiać się nad istnieniem innego rodzaju maszyn i ich potencjalnymi możliwościami.
Wracamy w ten sposób do relacji matematyka-informatyka. Czy nie jest tak, że pewne szersze, a niekiedy dobrze już opracowane i ‘przećwiczone’, teorie matematyczne, są dla informatyki cenne, bo pozwalają jej spoglądać w przyszłość…
Dopowiem na koniec, że moje „W tył zwrot” – niezależnie od powyższych wątpliwości – oznacza również dalszą otwartość na tezę, że [pojęcie liczby nie jest w informatyce niezbędne – zwłaszcza, jeśli informatykę będziemy rozumieć jako sztukę konstruowania i programowania maszyn operujących, koniec końców, na pewnych fizycznych sygnałach].
Zwracam się z uprzejmą prośba o wyjaśnienia/ odpowiedzi na pytania, które pozwolę sobie poprzedzić wstępem/ uzasadnieniem.
Podnosiłem już (w moich komentarzach) sprawę tego, że ta dyskusja wokół obecności ‘liczb’ w informatyce rozgrywa się bez wyjaśnienia ‘liczb pojęcia’, pomimo tego, że że pozostając:
-w zgodzie z różnymi filozoficznymi intuicjami (może mnie tu Profesor Marciszewski z błędu wyprowadzić)
– jak i w zgodzie (chyba – proszę o ewentualną korektę) z matematycznym rozumieniem „istoty” ‘liczb’ określonej przez swoisty (aksjomatyczny sposób) konstrukcji,
można ‘liczby’ różnego typu (nomen omen) „mnożyć” (i – o czym za chwilę – arytmetyki również).
W odpowiedzi przeczytałem, że:
„te obiekty (byty obecne w informatyce – przyp. km) są liczbami, lecz innymi niż „liczby matematyczne” i nie ma do niech zastosowania choćby arytmetyka Peano”
Zwracam jednak niniejszym uwagę, że to co ma do nich zastosowanie – czyli idealne (informatyczne) reguły przekształceń/działań nad ‘liczbami informatycznymi’ – też chyba (proszę o zarówno Filozoficzną jak i Matematyczną korektę) podpada pod definicję ‘arytmetyki’.
Z obserwacji dyskusji mam wrażenie, że „oczywistość” rozumienia pojęcia ‘liczb’ i 'arytmetyki’ okazała się zwodnicza, a próby podtrzymanie pierwotnie wysuniętych tez oparte są na od początku różnych (lub zmienianych w trakcje) sposobach ich rozumienia, oraz próbach rozstrzygania o „pierwotności” danego sposobu ich rozumienia w szczególności poprzez dociekanie tego „co miał Turing na myśli”.
Tymczasem nawet jeśli ważne jest dla mnie praktyczne podejście (stąd i także moje zainteresowanie w kryterium demarkacji liczb informatycznych i matematycznych) to sprawa ma chyba wagę (ściśle) filozoficzną (a na pewno rozstrzygnięcie powinno dokonać się z perspektywy obejmującej z boku zarówno ściśle matematyczne jak i stricte informatyczny ogląd – jeśli nie chce się tu popaść w jakieś paradoksy/ z logicznych powodów sprawy nie móc rozstrzygnąć).
Filozoficzne uporządkowanie i wyjaśnienia przydały by się właśnie dlatego, że kluczowe w dyskusji pojęcia używane były w dyskusji na różne sposoby (wskazując różne rozumienie)- niektóre argumenty (za lub przeciw) dotyczyły liczb tylko jakiegoś rodzaju (np. naturalnych) inne miały chyba za cel obrane liczby „w ogóle”. Przy czym jeśli chodzi o liczby „w ogóle” to chyba jednak chodziło (proszę o korektę) po prostu o w matematyce używane liczby (rzeczywiste, zespolone itd.) czy arytmetyki (Peano, Presburgera)
A NA PEWNO NIE ZWRACANO UWAGI NA TO, że (posłużę się prawniczą analogią) „katalog takich bytów jest otwarty” (‘arytmetyk’ i ‘liczb’). I za byty takiego rodzaju mogą podpadać jeszcze rozmaite inne (poza tymi z „nie-informatycznie”, matematycznego katalogu), jeśli posiadają jakieś istotne cechy/ własności – charakterystyczne dla idealnych konstruktów (liczb) których cała treść określa się poprzez podpadanie pod te reguły (skonstruowane zgodnie z określonymi zasadami).
Oto zatem i moje pytania/ wątpliwości „filozoficzne”, przepraszam, jeśli się w niektórych z nich powtarzam, ale odpowiedź na te pytani zdaje mi się kluczowa dla dyskusji:
-Czy jeśli proponowane informatyczne „zamienniki” liczb/arytmetyk mieszczą się w granicach reguły liczb/arytmetyk konstrukcji to nie oznacza, że można je liczbami/arytmetykami nazywać? A jeśli chodzi o „pierwotność” pojęcia to czy przypadkiem nie należało by określić właśnie granic (i praktycznego powodu wyodrębnienia). (I znowu się powtórzę: ta granica chyba nie ma się opierać na dociekaniu czy Turing miał na myśli liczby czy nie, ale być określona poprzez same zasady konstrukcji, i istotne cechy powstałych w zgodzie z nimi konstrukcji.)
-Czy konkatenacja (w Informatyce) nie może być uznana za część idealnego aksjomatycznego konstruktu określającego zasady działania na informatycznych bytach (o których chyba zasadnie można pisać ‘liczby informatyczne’)… ‘arytmetyki „informatycznej”’. ‘Arytmetyki’ bo konstrukcji tej bliżej do innych matematycznych rodzajów arytmetyk niż do „wszystkiego innego”?
„U Turinga występuje tylko takie liczenie — teoriomnogościowe, przez wskazanie funkcji jednoznacznego przyporządkowania jako dowód równoliczności.” – Byt określony jednoznacznie przez pozycję w idealnym szeregu – toż to (filozoficzna) definicja liczby wg wspomnianego już przeze mnie Cassirera.
-Co do cytowanej wypowiedzi Turinga i zamiany ‘numbers’ na ‘sequences’:
Sekwencja czego – znaków? Zatem dalej idealnych bytów uszeregowanych w dany sposób, na których możemy wykonywać działania zgodnie z aksjomatycznie określonymi zasadami. Czym to się rożni od (innych) arytmetyk tak, że nie może być (trafnie/ poprawnie) nazywana arytmetyką (informatyczną) na liczbach (informatycznych) operującą (bo nie znajduję przyczyny w definicji liczby, informatyki ani w niniejszej dyskusji)?
-„Faktycznie, gdy analizujemy pojęcie maszyny Turinga, możemy dojść do wniosku, że pojęcie to nie ma w sobie nic ‚liczbowego’: jest ono określone za pomocą bardziej elementarnych pojęć symbolu (z pewnego alfabetu), stanu (dyskretnego), taśmy (wypełnianej symbolami), głowicy (zmieniającej stany i zapisującej/zmazującej symbole) oraz tablicy przejść (wypełnionej rozkazami czysto symbolicznymi).”
Czy to nadal nie jest przypadkiem aksjomatyczny zespół reguł ,chyba nie różniący się od (innych) arytmetyk tak istotnie, by nie mógł być arytmetyką informatyczną nazywany?
„U Turinga występuje tylko takie liczenie – teoriomnogościowe, przez wskazanie funkcji jednoznacznego przyporządkowania jako dowód równoliczności.” – Byt określony jednoznacznie przez pozycję w idealnym szeregu – toż to (filozoficzna) definicja liczby wg wspomnianego już przeze mnie Cassirera.
To chyba często spotykany błąd. Wiem z czego on się bierze (tak, też się uczyłem z podręcznika Rasiowej) – w definicji jest mowa o równoliczności ze zbiorem liczb naturalnych. Ale z wykazania równoliczności zbiorów przez udowodnienie istnienia funkcji jednoznacznego przyporządkowania wcale nie wynika, że zobaczymy gdzieś „idealny szereg”. Relacja równoliczności jest relacją przechodnią, więc jak raz sobie „policzymy” liczbami naturalnymi jakiś nieuczesany zbiór, to dalej już on może nam służyć za liczydło. A przeliczalnych zbiorów bez naturalnie określonego porządku jest sporo (konkretnie ℵ₀)
Dziekuje za odpowiedź ale cały czas (niestety) mówimy o różnych „rzeczach”:
1. 'Liczbach „w oģóle”’ jako określonych aksjomatycznym systemem (choćby nawet cześć systemu cech brała się z wybranych własności rzeczywistych fenomenów) bytach w idealnym uszeregowaniu (nawet jeśli skończonym), „pozwalającym coś policzyć”, których „cała treść wyraża się w relacjach których są intelektualnym centrum” (nawet jeśli te relacje nie są równoważne arytmetyce Peano.
2.’Liczbach naturalnych’, 'rzeczywistych’ czy innych szczególnych przypadkach rezultatu postąpienia zgodnie z regułą, powołującą do matematycznego istnienia poszczególne rodzaje liczb (zgodnie z matematyczną definicją)
I od dłuższego czasu staram się uzyskać informację w jaki sposób konstukcja informatycznych bytów łamie te reguły. Bowiem tylko jeśli są one złamane (a nie wydaje mi się to zachodzić- zważywszy, że elementy wymienionej pod 1. „Filozoficznej konstrukcji” odpowiadają matematycznej regule tworzenia zbiórów liczb) użycie w stosunku do informatycznych bytów pojęcia 'liczb’ byłoby nietrafne.
Analogicznie sprawa się ma w przypadku arytmetyk.
Dlatego celne wydaje mi się w tym kontekście potraktowanie Informatyki jako części matematyki. Wtedy moglibyśmy przejść do porządku dziennego, nad tym, że mamy w Informatyce do czynienia z „liczbami informatycznymi” (także pewnie różnego rodzaju- ale żadnego nie równoważnego któremukolwiek ze zbiorów stosowanym w innych gałęziach matematyki) i 'arytmetyką informatyczną’ (o także pewnie innych własnościach niż odpowiedniki z pozostałej matematyki).
Dzięki terminologicznemu rozstrzygnięciu (jakiekolwiek by ono nie było- gdyby na przykład wskazać powód, dla którego 'byt informatyczny’ nie może być sklasyfikowany jako 'liczba’- powód wynikający z w/w reguły/matematycznej praktyki liczb tworzenia a nie z dociekań intencji Turinga;) można by dopiero dojść do praktycznych rozstrzygnięć:
– o tym czy więcej różni czy dzieli matematyczne i informatyczne liczby/arytmetyka i
– czy bardziej „opłaca się” pożyczać schematy postępowania przećwiczone w poza-informatycznej matematyce czy wypracowywać nowe (swoiste dla informatyki).
To byłoby chyba praktycznie pragmatyczne podejście a jednocześnie filozoficznie trafne.
Kwestia istnienia czy niebytu liczb/arytmetyki „w podstawach” informatyki wydaje mi się nie tylko mniej „praktyczna” ale bez rozstrzygnięcia filozoficznego rozumienia użytych terminów niemożliwa do rozstrzygnięcia.
Uwaga: stanowczo zastrzegam, że żaden z moich błędów nie mógł wynikać z przywołanego podręcznika, gdyż na oczy go nie widziałem (Cassirer pewnie też;) A jedynie z mojego mylnego rozpoznania sprawy. W oczekiwaniu na wyprowadzenie z mylnych przeświadczeń oczekuję kolejnych komentarzy
1. Czy pojęcie liczby (np. naturalnej) staje się zrozumiałe dopiero wtedy, gdy osadzimy je w teorii arytmetycznej?
Tak, arytmetyka jest niezbędna, byśmy mogli mówić o liczbach (a zwłaszcza liczyć z ich udziałem). Numer NIP, który ma każda firma, jest numerem tylko z nazwy i z pozoru. Wygląda jak liczba naturalna, ale operacje arytmetyczne na nim nie mają najmniejszego sensu – z dodania do siebie NIP-ów dwóch firm nic nie wynika, a już w szczególności nie będzie to NIP fuzji obu podmiotów. Jest to zatem tylko symbol (lub „identyfikator” – jak wyraża to druga litera skrótu) – równie dobrze można by było do identyfikacji podatników używać ciągów literowych. Podałem przykład wzięty z informatyki praktycznej, ale w tej teoretycznej jest tak samo.
Od liczb wymagamy, by się dało je osadzić chociażby w teorii grup (liczby całkowite). To dość łagodne wymaganie, ale niezbędne, by nie popaść w jakieś trywialne deklaracje w rodzaju „wszystko jest liczbą, a przynajmniej może nią być”.
2. Jakie mamy przyjąć kryterium odróżnienia informatyki od matematyki? Czy jest ono ostre?
Ja uznaję informatykę jako dział matematyki – i nie jestem w tym osamotniony. Tu powołam się na myśl wielkiego Kerberona Emtedryty, który odradzał zajmowanie się tym, co istnieje, bowiem „banalność istnienia została udowodniona zbyt dawno, by warto jej poświęcać choćby jedno jeszcze słowo”. Proszę mi tylko nie wytykać, że znowu jakieś bajki opowiadam – Stanisław Lem w kilku zdaniach ujął to, czego być może niejeden filozof nauki nie zdołałby jasno opisać w sążnistej pracy.
W naukach przyrodniczych na ogół jest tak, że odkrycie nowego ważnego bytu powoduje natychmiastowe powstanie nowej nauki. I tak mamy wirusologię, mamy genetykę, bakteriologię itd. Bo odkryto wirusy, geny, bakterie (itd.). W matematyce ten schemat też jest możliwy, ale to podejście raczej nie generuje fascynujących dyscyplin. Co innego, gdy założymy sobie nieistnienie. Powiedzmy, że chodzi o nieistnienie miar kątów i odległości. Dorzućmy do tego jeszcze nieistnienie relacji leżenia między (dotyczącej punktów). Gdy to wszystko ujmiemy geometrii, uzyskamy mowy dział matematyki, nazwany topologią. A topologia, jak mało która część Królowej Nauk, okazała się wielce płodną i pożyteczną.
Informatykę można opisać w sposób banalny: to taka matematyka, która zauważa istnienie komputerów. Ale to słaba definicja. Zdecydowanie lepsze będzie tu podejście emtedryckie – liczmy, ale bez założenia o istnieniu liczb, tak skończonych, jak i nieskończonych, a to liczenie nazwijmy „informatyką”.
Nie jest dobrym zwyczajem nieustanne wtłaczanie wciąż nowych rzeczy do starych worków. Dlatego bardzo niechętny jestem nazywaniu „informatyką” czegoś, co nijak nie przystaje do wcześniej przyjętego modelu. Obliczenia analogowe (jakie by one nie były) ani trochę nie są powiązane z modelem Turinga. Zwłaszcza że nie ma chyba żadnej (po)ważnej teorii okołoinformatycznej dotyczącej obliczeń na liczbach rzeczywistych. Nie dostarczyły jej komputery analogowe – one nie obliczają liczb, tylko funkcje. Zatem albo poszukajmy dla takich nauk innych nazw, albo przynajmniej dodajmy dookreślający przymiotnik – dajmy na to „informatyka analogowa” (pamiętając przy tym, że świnka morska nie jest po prostu rodzajem świnki).
Innymi słowy: ja uznaję, że pewne wyniki dotyczące liczb (a nie tylko ciągów symboli) mieszczą się w zakresie badań informatycznych.
Ja w uznaniu idę jeszcze dalej. Informatyka (również teoretyczna) jest nauką bardzo praktyczną i pożyteczną. Potrafi dostarczyć niesłychanie ważnych wyników dotyczących nie tylko liczb, ale też kolorów, kształtów a nawet rzeczy, o których się filozofom nie śniło. Tylko co z tego, gdy rozmawiamy o podstawach, a nie o wynikach?
3. Równoważność teorii funkcji rekurencyjnych i teorii maszyn Turinga (co do zakresu rozw. Problemów). Czy ta równoważność – a dodatkowo fakt, że uzyskując pewne wyniki w teorii maszyn Turinga posługujemy się własnościami liczb naturalnych – nie świadczy o niezbędności (a przynajmniej: wielkiej przydatności) kategorii liczby w informatyce teoretycznej?
Jeśli ta równoważność jest, to należy się cieszyć – mamy dwie teorie dające to samo, więc wzajemnie się potwierdzające. Ale warto też zauważyć, że turingowska informatyka jest jakby bardziej doceniana i chętniej stosowana, niż „podejście ufundowane na pojęciu liczby (naturalnej) i elementarnych operacjach arytmetycznych”.
Jeśli
fenomenów „powstałych” w ramach funkcjonowania maszyny powstałej z przepisu Turinga nie da się „osadzić w ramach teorii grup”
I
istnieje taki formalny warunek dla liczb (aby dało się je w tej teorii „osadzić”)
to sprawa byłaby chyba rozstrzygnięta?
Jeśliby takiego wymogu jednak nie było konieczny byłby konsens specjalistów od użycia pojęcia liczb aby go wprowadzić (aby móc ostatecznie orzec o tym, że w podstawach Informatyki liczb nie ma) – ale akurat argument, że w przeciwnym wypadku „wszystko mogłoby być uznane za liczbę” mogbyłby nie być dla matematyków przekonujący…