Obecny wpis ma charakter nietypowy, ponieważ przedstawiam w nim urywki dyskusji, która wynikła przy okazji analizy pewnego mojego tekstu nt. granic kodowania w informatyce (samego tekstu nie linkuję, ponieważ przygotowuję go do publikacji). Dyskusja była prowadzona drogą e-mailową, ale wspólnie z drugim jej uczestnikiem, postanowiliśmy udostępnić ją w blogu.
Dyskusja dotyczy niezbędności matematycznej kategorii liczby w szeroko pojętych badaniach informatycznych, obejmujących także metodologię i filozofię tej dyscypliny.
Ja uważam, że kategoria ta jest niezbędna.
I to zarówno w aspekcie syntaktycznym, gdy odwołujemy się do samych zapisów liczb w odpowiedniej notacji (tzw. numerałów), jak i w aspekcie abstrakcyjnym, gdy odwołujemy się do własności liczb rozumianych jako obiekty abstrakcyjne (np. takich własności liczb rzeczywistych, które gwarantują ciągłość zbioru R).
Mój oponent przekonanie powyższe traktuje co najmniej sceptycznie.
W przedstawionych dalej fragmentach rozmowy moje wypowiedzi są oznaczone jako PS (Paweł Stacewicz), zaś wypowiedzi oponenta jako Harry (co jest jego blogowym pseudonimem).
A oto zapis anonsowanej dyskusji:
1. (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. Obydwa pojęcia są niezbędne, o ile chcemy traktować informatykę szeroko, a nie tylko jako teorię i praktykę działania/wykorzystywania maszyn cyfrowych.
W informatyce rozumianej szeroko możemy rozważać chociażby maszyny analogowe, operujące na kodach rzeczywisto-liczbowych (de facto układy takie były konstruowane i opisywane teoretycznie przed erą maszyn cyfrowych); w przypadku obliczeń biologicznych też nie jest wykluczone, że przez odpowiednie układy są przetwarzane sygnały, którym odpowiadają liczby rzeczywiste; a są ponadto pewne przesłanki, żeby przyjąć, iż dla opisu sygnałów przetwarzanych przez komputery kwantowe są niezbędne liczby zespolone.
Można próbować ująć sprawę tak, że opis sygnałów przetwarzanych przez takie czy inne maszyny w kategoriach liczb jest tylko wygodnym zabiegiem teoretycznym…
Rzecz jednak w tym, że ten zabieg jest niezbędny do uprawiania informatyki teoretycznej, która w przeszłości inicjowała, a w przyszłości prawdopodobnie będzie inicjować, pewne rozwiązania praktyczne i fizyczne zarazem (np. komputery cyfrowe o takiej a takiej konstrukcji fizycznej).
2. (Harry)
Co do kwestii konieczności reprezentacji matematycznej (w informatyce), to powyższe Twoje wyjaśnienia nie bardzo przekonują mnie. 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?
3. (PS)
Powołam się na trzy argumenty:
– argument historyczny: fizyczne komputery cyfrowe nie zaistniałyby bez koncepcji uniwersalnej maszyny Turinga (która jest obiektem matematycznym, powiązanym z pojęciami liczby obliczalnej i nieobliczalnej; a w dodatku jest punktem wyjścia teorii obliczeń, czyli fundamentu informatyki teoretycznej).
– argument metodologiczny (obecny pośrednio wyżej): poprzez pojęcie algorytmu (objaśnianego m.in za pomocą pojęcia f. rekurencyjnych albo UMT; czyli obiektów matematycznych ) informatyka jest w sposób konieczny (tak mi się wydaje) częściowo przynajmniej matematyczna; niemożliwa do uprawiania bez narzędzi matematycznych.
– inny argument metodologiczny: bez rozważań/dowodów matematycznych dot. UMT, a także aktualnie nieskończonych reprezentacji liczb nieobliczalnych (czego dotyczy anonsowany we wstępie artykuł), nie dowiedzielibyśmy się niczego o (minimalnych) ograniczeniach technik cyfrowych.
4. (Harry)
Nie do końca mnie zrozumiałeś. Chodziło 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”. Dlatego wydaje mi się, że podane przez Ciebie (powyżej) argumenty są nie do końca trafne.
Nawiązywałem do zawartej w Twojej ostatniej wypowiedzi tezy:
opis sygnałów przetwarzanych przez takie czy inne maszyny w kategoriach liczb jest teoretycznie niezbędny
Wydaje mi się, że przyjmujesz ją w sposób mało krytyczny i wyciągasz z niej mocne filozoficzne wnioski lub metafory (jak np. ta o dualnej, liczbowo-fizycznej naturze programów). Nawet gdyby okazało się, że ze względu na swój praktyczno-inżynieryjny charakter (np. dwójkowy charakter impulsów elektrycznych) nie może istnieć inna informatyka niż „liczbowa” (w co zdają się powątpiewać niektórzy praktycy), to i tak z tego nie wynika, że reprezentacje liczbowe programów są niezbędne w ich teoretycznej charakterystyce. Dość dobitnie świadczą o tym niektóre twierdzenia o nierozstrzygalności (m.in. twierdzenia Grzegorczyka o nierozstrzygalności teorii konkatenacji). Wynika z nich, że można skutecznie posługiwać się pojęciem obliczalności bez używania kategorii liczby (i co za tym idzie – bez pojęcia liczbowej reprezentacji).
5. (PS)
Rozumiem.
Uznaję jednak, że rozróżnienie między liczbami naturalnymi i rzeczywistymi jest niezwykle ważne dla informatyki, bo pozwala uchwycić/wyrazić/wyjaśnić różnicę miedzy technikami/maszynami cyfrowymi i analogowymi. Nawet jeśli ktoś twierdzi, że prawdziwe maszyny analogowe nie istnieją, to najbardziej podstawowe uzasadnienie tego faktu musi czerpać z założenia, że nie istnieją obiekty fizyczne odpowiadające liczbom rzeczywistym. Wtedy jednak odwołuje się do własności liczb (twierdząc coś o istnieniu bądź nieistnieniu maszyn, czyli obiektów informatycznych).
Zapraszam serdecznie wszystkich Czytelników bloga do kontynuacji powyższej wymiany argumentów…
Paweł Stacewicz
Do powyższych argumentów dorzucę dwa spostrzeżenia — jedno czysto historyczne (I), drugie po części historyczne (II). Sformułuję też pewne przypuszczenie (III).
I.
Chociaż nie jest to argument wiążący filozoficznie, w szczególności zaś ontologicznie, to warto zauważyć, iż pierwsze urządzenia, a potem maszyny, informatyczne (wprawdzie nazwa „informatyka” powstała dopiero w XX wieku, ale myślę że można tu jej użyć) służyły do automatyzacji operacji arytmetycznych, czyli operacji na liczbach. Na przykład, mechaniczny arytmometr Leibniza z XVII w. pozwalał realizować dodawanie, odejmowanie, mnożenie i dzielenie liczb zapisanych dziesiętnie.
Dopiero stopniowo zaczęto dostrzegać, że te same układy fizyczne, które sprawdzają się przy mechanizacji arytmetyki, mogą służyć do przetwarzania obiektów innego rodzaju (jak np. wzory tkackie czy teksty). Mogą zaś służyć dlatego, że wspomniane obiekty daje się je reprezentować liczbowo (być może tylko na poziomie syntaktycznym, tj. na poziomie zapisu symbolicznego, ale jednak…)
Dzisiejsze zastosowania komputerów polegają na tym właśnie, że najprzeróżniejsze obiekty – które na pozór nie mają nic wspólnego ze sferą liczb – mogą zostać opisane liczbowo i dzięki takiemu właśnie opisowi mogą być efektywnie przetwarzane przez specjalne układy wewnątrz maszyn. Przy czym, z punktu widzenia człowieka, niektóre z tych opisów mają charakter „wysokopoziomowy” – gdy bezpośrednio, rozwiązując jakieś zadanie (np. obrót kształtu na ekranie komputera), opisuje się dany obiekt liczbowo (np. określając współrzędne liczbowe punktów składających się na wspomniany kształt); inne zaś mają charakter „niskopoziomowy” – gdy sama maszyna, niezależnie nawet od zamysłu człowieka, przypisuje obiektowi ciąg bitów (matematycznie: zer i jedynek) przetwarzanych przez wewnątrz-komputerowe układy najniższego poziomu.
Podsumowując, trzeba stwierdzić, że ewolucja maszyn i technik informatycznych, postępowała w kierunku od mechanizacji elementarnych operacji arytmetycznych na liczbach do automatyzacji działań na obiektach nieliczbowych. Te ostatnie jednak są reprezentowane wewnątrz komputerów cyfrowo i w takiej właśnie postaci są przetwarzane za pomocą układów bardzo podobnych do tych, które niegdyś służyły do mechanizacji działań na liczbach. To zaś może skłaniać do przekonania (a przynajmniej mnie silnie skłania), że czymś informatycznie pierwotnym są reprezentacje liczbowe i operacje arytmetyczne.
II.
Odniosę się jeszcze do następującej (nieco przeredagowanej) uwagi Harry’ego:
— Maszyny Turinga i algorytmy są obiektami typowo informatycznymi, w opisie których nie posługujemy się (lub ostrożniej: nie musimy posługiwać się) „językiem liczb”.
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).
Pomimo powyższego Turing widział potrzebę teoretycznej analizy swojej konstrukcji w kategoriach liczb.
Zinterpretował bowiem ciągi generowane przez ‘swoje’ maszyny jako dziesiętne reprezentacje pewnych liczb rzeczywistych – reprezentacje definiujące te liczby. Ogół tak zdefiniowanych liczb nazwał (rzeczywistymi) liczbami obliczalnymi. Spostrzegł dalej, że generujące je maszyny daje się ustawić w ciąg (przyjmując pewną metodę ich numeracji – znowu liczby!), i z tego powodu zbiór liczb obliczalnych jest przeliczalny, czyli równoliczny ze zbiorem liczb naturalnych.
Już to wystarczyłoby do stwierdzenia, że oprócz liczb obliczalnych istnieją inne liczby rzeczywiste: liczby nieobliczalne (które dopełniają zbiór liczb obliczalnych do pełnego continuum liczb rzeczywistych). Turing jednak przedstawił dodatkowo pewną procedurę definiowania liczb nieobliczalnych, która była wzorowana na argumentacji przekątniowej Cantora (nie jest to przy tym procedura efektywnego generowania l. nieobliczalnych).
Krótko mówiąc: analizując swoją konstrukcję w kategoriach liczbowych, 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).
Wracamy w ten sposób do (ahistorycznej już) kwestii niezbędności kategorii liczby w informatyce teoretycznej. Zgodnie z ustaleniami Turinga informatyce ograniczonej do analizy technik cyfrowych wystarcza przeliczalny zbiór liczb naturalnych (być może nawet, wbrew Turingowi, wystarcza wspomniana przez Harry’ego teoria konkatenacji – czyli, jak rozumiem, łączenia ze sobą pewnych ciągów symboli).
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.
III.
Być może wspomniana wyżej teoria konkatenacji (której nie znam) ma jakieś rozszerzenie, które prowadzi do teorii maszyn wykraczających swoimi możliwościami poza możliwości maszyn Turinga… Jest to ciekawe zagadnienie badawcze.
Jeśli jednak rozszerzenie to doprowadzi do zdefiniowania maszyn, które generują sygnały opisywane za pomocą liczb rzeczywistych, to rozszerzenie to będzie prawdopodobnie jakąś teorią liczb rzeczywistych (które to liczby już teraz przecież są definiowane na różne sposoby, np. za pomocą ciągów Cauchy’ego albo za pomocą przekrojów Dedekinda).
„To zaś może skłaniać do przekonania (a przynajmniej mnie silnie skłania), że czymś informatycznie pierwotnym są reprezentacje liczbowe i operacje arytmetyczne.”
Ewolucja moich poglądów zmierza w przeciwnym kierunku. Nabieram coraz silniejszego przekonania, że pojęcie liczby jest dla informatyki niepotrzebne. Programuję dużo i od bardzo długiego czasu (przeszło 40 lat), ale nie pamiętam kiedy ostatnio miałem potrzebę w programie coś policzyć. Kiedyś, gdy jedynym językiem programowania był FORTRAN, teksty programów przepełnione były liczbami i symbolami arytmetycznymi. To się zmieniło, choć rozwiązywane problemy wciąż są podobne.
Sprawdziłem też, czy to co napisałem wyżej, nie jest tylko moim złudzeniem. Wziąłem kod dużego i powszechnie używanego programu (pakiet „Libre Office”) i poddałem go analizie. Tekst źródłowy jest wielki, ma objętość jednego gigabajta i przeszło 16 milionów linijek. To tyle, co około półtora tysiąca książek klasy „cegła akademicka”, całkiem pokaźna biblioteka. Operacja dodawania użyta została tam około 50 tysięcy razy. Na jeden tom przypada więc
ledwie 30 dodawań — nie są więc to „książki o dodawaniu”.
Potem przyjrzałem się bliżej znalezionym plusom. Rzecz jasna nie wszystkim, tylko losowo wybranym. Wiele z nich użyto nie z konieczności, lecz niejako „z przyzwyczajenia”. Mamy nadreprezentację dodawań postaci „x + 1”. A to nie jest w ścisłym sensie dodawanie, lecz inkrementacja. Starsze języki programowania operacje na grupach danych potrafiły wykonywać tylko w jeden sposób — po wojskowemu: w szeregu zbiórka, kolejno odlicz, robimy coś z pierwszym elementem, następnie z tym o numer wyższym i tak do końca. Czyli do odliczonej liczby. We współczesnych językach instrukcja brzmi zazwyczaj „weź wszystkie elementy spełniające podane kryterium i zrób z nimi coś”. Zwykle nas nie interesuje, w jakiej kolejności robota będzie wykonana, więc komputer robi jak mu wygodnie. I wcale nie musi być tak, jak piszą w starych podręcznikach, że „kompilator zamieni to na kod maszynowy, który ma postać ciągu liczb i wykonywany jest przez procesor będący fizyczną emanacją maszyny Turinga”. Współcześnie zadanie może być wykonywane w systemie rozproszonym, przez wiele maszyn, które wzajemnie wiele o sobie nie wiedzą, a sam przebieg wykonania nie jest nikomu z góry wiadomy.
Z poglądem, że „reprezentacje liczbowe są w komputerach pierwotne”, też nie mogę się zgodzić. To my nadaliśmy im taką interpretacje. Komputery przetwarzały i przetwarzają sygnały elektryczne, to się nie zmieniło. A że pisząc o tym na papierze wygodnie było te stany napięć ponumerować i dalej używać liczb — to inna sprawa. W lesie koło mnie ponumerowano niektóre drzewa malując na nich cyfry pomarańczową farbą. Czy to znaczy,
że leśnicy będą teraz wykonywać na nich operacje matematyczne przy użyciu piły łańcuchowej?
Na koniec o oświeceniowych maszynach mechanicznych, uznawanych często za sam początek informatyki. Leibniz skonstruował arytmometr, bo odczuwał potrzebę liczenia (Calculemus!). Ale arytmometr nie jest komputerem, tak jak dźwignia (formalnie: maszyna prosta) nie jest maszyną. Istotą informatyki jest realizacja zapisanego algorytmu, a nie wykonywanie jednostkowych operacji arytmetycznych. Początek informatyki można zobaczyć na filmie poniżej. Osiemnastowieczny zegarmistrz w mechanicznym urządzeniu zrealizował to, co mają współczesne komputery — zapis sekwencji operacji, wywoływanie wcześniej zdefiniowanych funkcji (procedur), operacje porównywania i podejmowania decyzji itd. Realizacja jest częściowo cyfrowa (lepiej powiedzieć: dyskretna), częściowo analogowa. Ale liczb w tym nie ma.
Proponuję – aby temat nam się za bardzo nie „rozjechał” – pozostać na razie w obrębie standardowej koncepcji obliczalności (tj. związanej z pojęciem maszyny Turinga). Chciałbym też jeszcze raz podkreślić różnicę między dwiema kwestiami: 1) niezbędności kategorii liczby w (standardowej) teorii obliczalności i 2) użyteczności tej kategorii w informatyce. Rozumiem, że temat dotyczy zasadniczo 1). Dlatego spostrzeżenie, że „Turing widział potrzebę teoretycznej analizy swojej konstrukcji w kategoriach liczb”, choć zasadniczo słuszne, raczej niczego istotnego nie wnosi do tej akurat dyskusji. Do obliczalności można oczywiście podejść czysto arytmetycznie (to było wiadomo jeszcze przed „wynalezieniem” maszyny Turinga). My pytamy się, czy jest to teoretycznie konieczne.
Żeby posunąć nieco ten temat do przodu, przytoczę zwięzłe omówienie (S. Krajewskiego) koncepcji Grzegorczyka:
„Algorytmiczność sprowadza się do operowania zapisami w sposób ujęty przez wyraźnie jednoznacznie podane przepisy postępowania. W najnowszym okresie twórczości Grzegorczyk podjął badanie teorii konkatenacji (czyli operacji zestawiania dwu tekstów, czyli ciągów symboli, w jeden tekst, w którym tekst następny staje się kontynuacją pierwszego), zaproponowanej w latach dwudziestych przez Tarskiego. Uzyskał zaskakujący wynik: prosta teoria tego pojęcia, choć wydaje się słabsza od słabej arytmetyki, jest również nierozstrzygalna […], a w dowodach metamatematycznych może zastępować i metamatematykę, i elementarną matematykę. Zamiast obliczalności Grzegorczyk wolał operować 'bardziej epistemologicznym’ pojęciem efektywnej rozpoznawalności właściwości tekstów lub relacji między tekstami. 'Empiryczna’ relacja konkatenacji dwóch wyrażeń zostaje potraktowania jako podstawowy zabieg służący do rozpoznawania właściwości bardziej złożonych. Całe rozumowanie przeprowadzone zostaje bez odwoływania się do pośrednictwa arytmetyki. Jest to zgodne z podejściem stosowanym w teoretycznej informatyce.” (S. Krajewski, „Andrzej Grzegorczyk (1922-2014)”, „Studia Semiotyczne”, XXVIII-XXIX(2015), s. 63-68).
Grzegorczyk wykazał, że w teorii obliczalności można się obyć bez liczb. Jarek pokazał, że można się bez nich obyć w praktyce informatycznej. Czy trzeba jeszcze czegoś więcej do odrzucenia tezy, że liczby są w informatyce konieczne? :)
Ciekaw jestem, jak Jarek odróżni – na poziomie metodologicznym – maszyny cyfrowe od analogowych, nie powołując się na różnicę między liczbami naturalnymi i rzeczywistymi? Chodzi mi o poziom metodologiczny, a nie praktykę programowania, z której wynika, że coraz rzadziej w realnych programach stosuje się (wprost) operatory arytmetyczne, liczbowe typy danych etc…
Ciekaw też jestem (trzeba będzie poczytać…), czy Grzegorczyk wykazał, że zbiór problemów rozwiązywalnych w modelu obliczeń określonym przez teorię konkatenacji pokrywa się ze zbiorem problemów rozwiązywalnych w modelu Turinga… (Rozumiem,że wykazał, iż istnieją w t. konkatenacji pr. nierozstrzygalne, a to nie to samo co wyżej). Gdyby nie wykazał tego pierwszego, to musiałby uzasadnić pogląd, że model obliczeń oparty na teorii konkatenacji lepiej przystaje do realnych obliczeń cyfrowych niż model Turinga. W szczególności, że określa węższe ograniczenia wszelkich realnych technik cyfrowych niż model Turinga. To byłby niesamowity wynik… W konsekwencji tezę Churcha-Turinga należałoby przeformułować tak, że efektywnie obliczalne jest to co można obliczyć zgodnie z modelem konkatenacji (teza Grzegorczyka…).
Jestem tu ciutkę sceptyczny. Są w informatyce słabsze od turingowskiego modele (jak np. automaty skończone czy automaty ze stosem) i stosuje się je do opisu pewnych szczególnych technik informatycznych, ale nie znaczy to, że nie ma technik silniejszych (które podpadają pod model Turinga). Podobnie „słaby” może być model oparty ma teorii konkatenacji. Są to jednak tylko moje przypuszczenia…
To akurat jest bardzo proste (odróżnienie) – maszyny cyfrowe są automatami stanów skończonych. W metodologicznym ujęciu termin „technika cyfrowa” zawsze funkcjonował niezależnie od „techniki komputerowej”. Technika cyfrowa prężnie rozwijała się w latach siedemdziesiątych, kiedy nie myło jeszcze mikroprocesorów, choć duże komputery (mainframe) były znane. Z tzw. bramek logicznych (funktorów) konstruowano urządzenia realizujące nieraz bardzo złożoną logikę. Ale liczenia w tym na ogół nie było. Ani cyfr. Pojęcia „zero logiczne” i „jedynka logiczna” w technice cyfrowej używane są równie często, co „stan wysoki” i „stan niski”. Można zauważyć, że z tego, że coś jest cyfrowe wcale nie wynika, że jest też liczbowe.
Maszyny analogowe nie mają przeliczalnej liczby stanów – i dlatego są poza zainteresowaniami „informatyki w sensie Turinga”. W maszynach analogowych zdarzają się procesy podejmowania binarnej decyzji (w układach komparatorów), jednak przesłanki do tych decyzji nie podlegają teoriom obliczalności.
Bardzo się cieszę, że Jarek tak skutecznie dostarcza nam prostych odpowiedzi na nasze skomplikowane pytania :)
Jarek: maszyny cyfrowe są automatami stanów skończonych.
W ujęciu matematycznym odpowiadają im obiekty o skończonej liczbie stanów, skończonej liczbie symboli alfabetu i nieskończonej taśmie czyli maszyny Turinga. Maszyny Turinga operują na skończonych ciągach symboli i generują wynikowe skończone (choć dowolnie długie) ciągi symboli, którym odpowiadają liczby naturalne. Nawet jeśli będziemy interpretować generowane wyniki jako niewymierne liczby obliczalne, to i tak ich zbiór jest równoliczny ze zbiorem N, więc w jakimś sensie mamy sprowadzalność do liczb naturalnych. Specyfika problemów rozwiązywalnych przez maszyny cyfrowe/turingowskie jest ponadto taka, że ich rozwiązanie ogólne, będące zbiorem par (dana, wynik), jest – przy każdej metodzie kodowania – liczbą obliczalną. Wszystkie te fakty przemawiają, moim zdaniem za tym, że metodologiczna analiza układów cyfrowych/turingowskich, wymaga posługiwania się liczbami naturalnymi i w pewnym sensie liczby te wystarczają.
Jarek pisze: Maszyny analogowe nie mają przeliczalnej liczby stanów – i dlatego są poza zainteresowaniami „informatyki w sensie Turinga”…
Nie mają przeliczalnej liczby stanów, a fizycznie rzecz ujmując pozwalają generować sygnały ciągłe. Jak te sygnały można opisać matematycznie? Tylko za pomocą liczb rzeczywistych (conajmniej).
A zatem różnica między maszynami analogowymi (nimi też interesują się informatycy-teoretycy) i cyfrowymi – w ujęciu matematycznym – polega na konieczności ich opisu (w różnych aspektach) za pomocą innego rodzaju liczb: raz naturalnych, raz rzeczywistych.
Może jestem uparty jak osioł, bo w sumie powtórzyłem się (to samo jest we wpisie zagajającym dyskusję). Ale moja interpretacja powyższych uwag Jarka jest właśnie taka jak wyżej.
Wracam gotować bigos, :)
Jeśli chodzi o to, czy coś można (w sensie: da się) opisać w ten czy inny sposób, to pewnie nie ma między nami zasadniczych różnic. Ale:
1. Układy cyfrowe będące automatami stanów skończonych, a zbudowane z funktorów logicznych, nie odpowiadają wprost maszynom Turinga. Opisywane z zewnątrz, traktowana jako czarna skrzynka, to samo (prawie to samo) mogą robić mikroprocesory — i dzisiaj technika zwykle idzie tą drogą. Jednak utożsamienie ich również w opisie teoretycznym, to wielkie nadużycie, wymagające zbyt daleko idących uproszczeń i przyjęcie całkiem niepotrzebnych założeń, w dodatku sprzecznych z tymi, które poczyniliśmy wcześniej przy konstruowaniu modelu zwanego maszyną Turinga. Dlatego też układy takie dorobiły się własnego opisu teoretycznego, całkiem niezależnego od „maszynoznawstwa Turinga”.
2. Wspomniane wyżej układy da się analizować tym samym aparatem teoretycznym, co maszyny analogowe. Z punktu widzenia elektronika w ogóle mogą one być tym samym. Ale maszyna analogowa tylko może, lecz nie musi przetwarzać informacji możliwych do opisania wyłącznie sygnałami ciągłymi. Tu tak nie jest — do opisu wystarczy „stan wysoki” i „stan niski”. Słusznie więc porzucono niewygodny aparat i skonstruowano taki, który przystaje do opisywanego obiektu (jeśli ktoś chce, to obiektu dualnego: fizycznego i logicznego).
Morał z tego płynie taki, że nie warto przykładać do wszystkiego tego samego narzędzia. Model Turinga legł u podstaw informatyki, był czas, że wyjaśniał wszystko, co ta nauka dawała praktyce. Niezaprzeczalne jest, że uporządkował i uprościł myślenie o wielu rzeczach. Jednak trwając wyłącznie przy tym modelu, a także stosując reprezentację liczbową tam, gdzie istnieje bardziej odpowiedni opis, można narobić w nauce niezłego bigosu.
Pawle, zgadzam się z dwoma ostatnimi akapitami Twojego wpisu :)
O ile mi wiadomo, Grzegorczyk tego nie wykazał. Być może w ogóle nie rozważał kwestii, czy da się ogólnie zdefiniować pojęcie obliczalności wyłącznie w kategoriiach konkatenacji, bez użycia arytmetyki. Natomiast wykazał, że można (co najmniej w kontekstach metateoretycznych) posługiwać się tym pojęciem bez użycia arytmetyki.
Nieco na marginesie naszej dyskusji dodam, że sam problem sformułowany przez Pawła wydaje mi się bardzo ciekawy: czy istnieje konkatenacyjna teoria algorytmu (czy też: obliczalności, rozwiązywalności, rozstrzygalności) alternatywna względem teorii turingowskiej i równoważna z nią w tym sensie, że generuje ten sam zbiór problemów rozwiązywalnych? Nie znam odpowiedzi na to pytanie i nawet nie wiem, czy były prowadzone takie badania (na swoje usprawiedliwienie mam tylko tyle, że nie jestem informatykiem :)). Ale to temat raczej na inną okazję…
Istnieje język programowania „Whitespace”, stworzony kilkanaście lat temu i opublikowany z datą 1 kwietnia. Do zapisu kodu programu w tym języku używa się tylko trzech symboli: spacji, tabulatora i znaku końca wiersza. Wszystkie te symbole są niewidoczne na ekranie czy wydruku, stąd nazwa języka. Pozostałe znaki, jak na przykład litery i cyfry, umieszczone w zapisie programu, są ignorowane przez kompilator i traktowane jako komentarz. Lista pojęć pierwotnych języka jest bardzo uboga, w szczególności nie zawiera liczb ani arytmetyki. Mimo tego Whitespace jest językiem zupełnym, to znaczy, że da się w nim opisać i rozwiązać te same problemy, jakie rozwiązuje (teoretycznie) maszyna Turinga, a (praktycznie) program napisany w „porządnym” języku, takim jak Python, Perl czy C. Tworzenie (definiowanie) nowych pojęć w Whitespace kojarzy mi się z konkatenacją — do znanego ciągu musimy dodać sekwencję niewidocznych znaków i nadać całości nowe znaczenie (w ten sposób da się stworzyć choćby pojęcie liczb).
Być może znowu udało mi się dać odpowiedź na jakieś pytanie (co by mnie niezmiernie cieszyło), choć odpowiedź ta tym razem nie musi być prosta — algorytmy opisane w Whitespace z prostotą nie mają wiele wspólnego.
(1) Powiedzenie o dualnej, liczbowo-fizycznej, naturze programów wydaje mi
się oczywiste i nie mające w sobie nic filozoficznego (jak to przypisuje
rozmówcy Harry w kom.4). Program czasem pojmujemy jako algorytm przełożony
na instrukcje operacji na liczbach, a więc jako pewien tekst, innym zaś
razem — jako proces fizyczny polegający na realizowaniu instrukcji przez
serie impulsów, np. elektrycznych. Kto ma na ten drugi sens lepsze
określenie, zapobiegające wieloznaczności, zasłuży się dobrze tej dyskusji,
dzieląc się swoją propozycją. Przejawem fizyczności (jeśli dobrze rzecz
rozumiem) byłaby chyba rola kompilatorów, które program napisany w jakimś
języku wyższego rzędu „tłumaczą”, w ostatecznej instancji, na kod maszynowy
wywołujący ciągi impulsów.
(2) Harry uważa (też w kom.4), że „reprezentacje liczbowe programów nie są
niezbędne w ich teoretycznej charakterystyce. Dość dobitnie świadczą o tym
niektóre twierdzenia o nierozstrzygalności (m.in. twierdzenia Grzegorczyka
o nierozstrzygalności teorii konkatenacji). Wynika z nich, że można
skutecznie posługiwać się pojęciem obliczalności bez używania kategorii
liczby (i co za tym idzie bez pojęcia liczbowej reprezentacji).”
Uwadze autora tych słów polecam art. A.Grzegorczyka i K.Zdanowskiego
„Undecidability and Concatenation”, 2007, w bazie danych:
https://www.researchgate.net/publication/264872979_Undecidability_and_Concatenation.
Pseudonim zapożyczyłem z dialogu Kartezjusza „Poszukiwanie prawdy przez
światło naturalne”. Występują w nim trzy osoby: Eudoks, Epistemon i
Poliander. Eudoks, to ktoś mający właściwy (gr. „eu” — dobry) pogląd (gr.
„doxa”), to jest, pogląd ukształtowany według metody kartezjańskiej.
Epistemon to ktoś o rozległej wiedzy (gr. episteme) wyniesionej ze szkół,
ale mało skłonny do odkrywczych poszukiwań. Poliander (połączenie greckich
nazw „wielość” i „człowiek” („andros”) reprezentuje nie tyle wiedzę, co
zdrowy rozsądek (w języku Kartezjusza „światło naturalne”) jednego z wielu
zwykłych ludzi. Chętnie pyta, a jeśli coś mylnie zrozumie, nie ma oporów w
przyznaniu się do pomyłki.
Autorowi tego komentarza brakuje zaawansowanej wiedzy informatycznej, ale
nie brakuje naiwnej ciekawości, przyjaznej dla zdrowego rozsądku. Stąd
sympatia dla Poliandra. Łączę od niego świąteczne pozdrowienia dla
uczestników obecnej dyskusji — PA.
Ad (1) Wydaje mi się, że ta „oczywistość” jest właśnie przedmiotem naszej dyskusji. Znów się powtórzę: z faktu, że jakiś fizyczny układ (np. program) może być jednoznacznie reprezentowany w języku arytmetyki NIE wynika, że ten układ MA NATURĘ liczbową (a więc – nie wynika, że sam program jest w istocie strukturą liczbową). Poza tym sformułowanie „dualna natura programu” sugeruje znacznie więcej: a) że ta fizyczno-liczbowa dwoistość jest jakąś specyfiką programów (ale przecież na tej samej zasadzie można by mówić o „dualnej naturze” wszelkich tekstów, a może i każdego układu przedmiotów materialnych) oraz b) że na podobnej zasadzie nie można by odróżnić jeszcze innych ontologicznie kluczowych aspektów programów (czy nie można by wyróżnić jeszcze np. psychologicznego aspektu związanego z tworzeniem programu; dlaczego więc natura programu komputerowego ma być „dualna”, a nie dajmy na to „triadyczna”?). Stąd moja uwaga, że to zdanie (o dualnej naturze programów) jest nie tylko kontrowersyjne ze względu na dyskutowaną tu jego konsekwencję (że liczby są niezbędne w programowaniu), ale też budzi dodatkowe skojarzenia, które mogą być potraktowane jako jego bardzo silne presupozycje filozoficzne.
Ad (2) Poliandrze, dziękuję, zapoznałem się już kiedyś z tym artykułem. W tym kontekście również powtórzę się: o ile mi wiadomo, Grzegorczyk nie stawiał ogólnego problemu „konkatenacyjnej teorii obliczalności”. Jednakże może warto podkreślić, że wspomniana przez Ciebie słabość TK jest w kontekście metodologii nauk dedukcyjnych dużą zaletą. Jeśli dobrze rozumiem tę kwestię, chodzi o to, że każda teoria zawierająca TK (a więc również arytmetyka Peany) jest nierozstrzygalna i za pomocą metody Grzegorczyka można to wykazać bez potrzeby odwoływania się do arytmetyki. Innymi słowy, arytmetyka nie jest konieczna w dowodzie twierdzenia Goedla. Być może więc nie jest też konieczna w informatyce? Dzięki argumentom i przykładom Jarka obecnie jeszcze bardziej skłaniam się do przekonania, że tak jest właśnie. Wydaje mi się, że teza o teoretycznej konieczności arytmetyki w informatyce nie znajduje żadnego merytorycznego uzasadnienia.
Cóż, nadszedł też czas na świąteczne wyłączenie się Harry’ego od spraw teoretycznej filozofii. Sprawdzę, czy są nowe komentarze dopiero po Świętach. Bardzo dziękuję wszystkim uczestnikom tej dyskusji za inspirującą wymianę myśli. Pozdrawiam Was świątecznie!
Cóż, nadszedł też czas na świąteczne wyłączenie się Harry’ego od spraw teoretycznej filozofii. Sprawdzę, czy są nowe komentarze dopiero po Świętach. Bardzo dziękuję wszystkim uczestnikom tej dyskusji za inspirującą wymianę myśli. Pozdrawiam Was świątecznie!
W SPRAWIE BIGOSU :)
Jarek napisał wczoraj:
< Morał z tego płynie taki, że nie warto przykładać do wszystkiego tego samego narzędzia. Model Turinga legł u podstaw informatyki, był czas, że wyjaśniał wszystko, co ta nauka dawała praktyce. Niezaprzeczalne jest, że uporządkował i uprościł myślenie o wielu rzeczach. Jednak trwając wyłącznie przy tym modelu, a także stosując reprezentację liczbową tam, gdzie istnieje bardziej odpowiedni opis, można narobić w nauce niezłego BIGOSU. >
Do(Od)powiem tak:
Właśnie… Czy chcemy, czy nie chcemy, informatyczny bigos ma coraz więcej składników. Wrzucamy do niego różne języki programowania, rozwiązania sprzętowe, matematyczne modele (i mikromodele) obliczeń…
Moim zdaniem jednak, wciąż jego esencją pozostaje staromodna koncepcja Turinga.
Wesołych Świąt!
Nie włączam się głębiej w dyskusję, w poczuciu braku dostatecznej
kompetencji tak w informatyce jak w matematyce. Paru rzeczy nie rozumiem,
więc zabieram głos w formie pytań, licząc na to, że za taki laicki wkład w debatę będę wynagrodzony zdobyciem odpowiedzi.
(1) Czy można w informatyce zrezygnować z takich kodów jak np. ASCII? Jeśli
chcemy wydrukować np. wykrzyknik, to trzeba spowodować, żeby coś tam w
komputerze utworzyło konfigurację impulsów 00100001 czyli fizyczny zapis
liczby dziesiętnej 33. Czy bez takich kodów liczbowych można się obejść w
informatyce? I zastąpić je np. jakimiś kodami z teorii konkatenacji?
(2) Czy da się przekonująco sparafrazować tytuł Turinga (1936) ON COMPUTABLE
NUMBERS, WITH AN APPLICATION TO THE ENTSCHEIDUNGSPROBLEM? Czy zamiast
„numbers” można wpisać „strings of symbols”? Czym wtedy zastąpić przydawki
„computable” i „uncomputable”?
(3) Grzegorczyk pisze, że teoria konkatenacji „is essentially weaker than
the Robinson arithmetic Q”. Uczestnika obecnej dyskusji, który powołuje się
na Grzegorczyka, prosiłbym o wyjaśnienie: czy poprawnie rozumiem zwrot
„essentially weaker”? A rozumiem go tak: teoria T jest istotnie słabsza od
teorii T*, gdy każde twierdzenie teorii T jest dowodliwe w T*, ale nie
odwrotnie. Jeśli moje rozumienie jest poprawne, i w tym sensie TK jest
słabsza od Q (tj. Peano bez aksjomatu indukcji), to mam kolejne pytania.
(a) Jak porównywać pod względem mocy dedukcyjnej teorie mówiące o
różnych dziedzinach? Jedna o liczbach, druga o fragmentach tekstów?
Trzeba by w tym celu zinterpretować jedną w drugiej. Ale jeśli TK jest
interpretowalna w Q to czy nie jest jakąś arytmetyką w przebraniu?
(b) Jeśli TK jest słabsza w suponowanym tu sensie nawet od Q, to jaki z niej
pożytek w porównaniu np. z arytmetyką Peano? Wynik Grzegorczyka jest
interesujący metamatematycznie, bo pokazuje jak trudno jest uzyskać
rozstrzygalność, gdy jej nie ma nawet teoria tak słaba. Więcej o doniosłości matematycznej mówi pouczający komentarz Harry-ego na temat TK (w
odpowiedzi na moje pytania). Zgadzam się z tą oceną. Ale czy to
upoważnia do wniosku, że da się uprawiać informatykę bez arytmetyki?
P.S. Tekst Grzegorczyka, to którego się tu odwołuję (zob. s.19) znajduje się
pod adresem:
https://www.researchgate.net/publication/264872979_Undecidability_and_Concatenation
(1) Jeśli ktoś u zarania dziejów informatycznych chciał wydrukować wykrzyknik albo inny znak, musiał wysłać depeszę do podłączonej do komputera linii dalekopisowej. Tak to się wtedy odbywało — nikt nie miał czasu na konstruowanie urządzeń wejścia/wyjścia, wzięto co było dostępne. Dalekopisy posługują się kodem Baudota, wymyślonym pod koniec XIX wieku. Nominalnie jest on 5-bitowy, czyli w pięciu kolejnych odcinkach czasu prąd może płynąć lub nie — i to niesie informację o znaku. Nominalnie, bo czasem do przekazania znaku trzeba nie 5, a 10 lub 15 impulsów. To skomplikowana sprawa i nie warto opisywać tu wszystkich szczegółów kodowania. Dość powiedzieć, że nikomu nie przyszło do głowy kojarzyć tych impulsów z liczbami. Baudot być może nawet nie wiedział co to liczby binarne — gdy się wszystko uporządkuje zgodnie z porządkiem numerycznym, kolejność liter ani trochę nie przypomina kolejności w alfabecie. Prosta odpowiedź zatem brzmi: wartości liczbowe nie mają znaczenia dla informacji takich jak tekst.
We współczesnym kodowaniu ASCII jest większy porządek, litery ułożone są po kolei zgodnie z alfabetem. Komuś, kto nie ma wiedzy historycznej może się wręcz wydawać, że tak być musi, że to liczby rządzą znakami. Błąd.
Napisałem taki krótki program w języku C:
void main() {char x;
for (x = 'a' ; x <= 'n'; x++) {
printf("%i\n", x);
}
}
Występuje w nim zmienna „x” zadeklarowana w typowy sposób jako najkrótsza liczba typu „integer”. Używam jej jako licznika pętli. Ale w tej pętli jako wartość początkową podstawiam literę „a”, potem każę przechodzić do kolejnych liter alfabetu, aż do osiągnięcia „n”. W pętli każę drukować, ale nie wartości licznika (które są tu literami), tylko liczbowe wartości kodu. Efektem działania programu jest wydrukowanie liczb od 97 do 110, jedna pod drugą. Czyli wszystko stoi na głowie — liczymy literami a gadamy cyframi! Całkiem odwrotnie niż w szkolnych zadaniach z informatyki i w powszechnych mniemaniach na temat życia wewnętrznego komputerów.
Pytanie „czy można się obejść” ja bym wolał zastąpić pytaniem „czy warto”. Praktyka wykazuje, że często warto — łatwiej mówić o literach, tekstach, kolorach czy dźwiękach — jeśli właśnie przetwarzaniem takich informacji ma zajmować się program. Ale nie należy popadać w skrajność — program do księgowości czy obliczeń inżynierskich nie będzie przecież zapisywał danych w sposób podporządkowany teorii konkatenacji. W mniej praktycznych przypadkach przypuszczam, że można i tak, i tak (ale gdzież mi do Grzegorczyka).
Oto moje – krótkie już – odpowiedzi na pytania Poliandra.
Ad (1) Seria impulsów elektrycznych 00100001, jeśli nie jest rezultatem użycia jakiegoś kodu, NIE jest fizycznym zapisem czegokolwiek. Jeśli zaś jest rezultatem użycia kodu ASCI, to jest fizycznym zapisem znaku „!”. I tyle. Nie ma tu żadnej KONIECZNOŚCI odwoływania się do liczb.
Ad (3) Tak.
Ad (3)(a) Na tej samej zasadzie można by powiedzieć, że arytmetyka jest rozbudowaną teorią konkatenacji w cyfrowym przebraniu.
Ad (3)(b) Nie upoważnia. Jednakże ciężar dowodu spoczywa na zwolenniku tezy o niezbędności arytmetyki w informatyce. Harry i Jarek jedynie pokazali, że nie widać dla niej – jak dotąd – żadnego należytego uzasadnienia.
Odnośnie odpowiedzi Harry’ego na (3)(b):
Harry i Jarek nie pokazali, że nie widać należytego uzasadnienia dla niezbędności kategorii liczby (i arytmetyki) w informatyce i jej metodologii, ponieważ zdają się przymykać oczy na następujące fakty metodologiczne, dotyczące autentycznej i efektywnej aktywności badawczej informatyków-teoretyków:
[1] formalna teoria obliczeń i wchodzące w jej zakres modele obliczeń stanowią część inf. teoretycznej (być może nawet: jej jądro),
[2] definiując, analizując i odnosząc do praktyki powyższe modele informatycy-teoretycy używają aparatu funkcji rekurencyjnych oraz rzeczywistych funkcji rekurencyjnych, które są określone odpowiednio na liczbach naturalnych (m. obl. dyskretnych/cyfrowych) i rzeczywistych (m. obl. ciągłych/analogowych). Definicje tych funkcji zakładają elementarną arytmetykę,
[3] powyższe modele są stosowane w metodologii informatyki powszechnie i efektywnie (pozwalają np. określać górne ograniczenia realnych technik komputerowych),
[4] teoria konkatenacji jest pewną wstępną propozycją, co do której wielu rzeczy nie wiadomo: np. czy model obliczeń, który byłby stworzony na jej podstawie jest równoważny pod względem zakresu rozw. problemów modelowi funkcji rekurencyjnych (dla ob. dyskretnych); a także czy ma ona jakieś efektywne (nie wymagające wprowadzenia liczb rzeczywistych) rozszerzenia, które pozwalałaby zdefiniować model obl. analogowych.
A zatem przyjmując (pragmatyczne?) kryterium zgodności filozoficznych wniosków z autentyczną praktyką badawczą informatyków-teoretyków (i tą współczesną, i tą doniosłą historycznie), nie widać, aby matematyczna kategoria liczby była w informatyce niepotrzebna. Wręcz przeciwnie: wydaje się być niezbędna.
(I) Paweł dodał (w ostatnim wniosku swojego ostatniego komentarza) operator „Wydaje się…” do tezy o niezbędności arytmetyki w informatyce (krótko: NAwI). Takie osłabienie jego początkowej tezy sprawia, że staje się ona jedynie przypuszczeniem sugerowanym przez dotychczasową praktykę badawczą informatyków-teoretyków. Odmienne przypuszczenie – sugerowane m.in. przez dotychczasowy kierunek rozwoju praktyki programowania – wyraża Jarek. To dość istotnie zmienia sytuację polemiczną; trudno w niej już twierdzić kategorycznie (czy też z poczuciem oczywistości, jakie np. wyraził Poliander), że „programy komputerowe mają dwoistą, fizyczno-liczbową naturę”.
(II) Dzięki tej dyskusji otrzymaliśmy też od Pawła (w jego ostatnim komentarzu) dość wyraźne sformułowanie jego argumentu za tezą NAwI. W skrócie wygląda on tak: arytmetyka jest w informatyce niezbędna, gdyż teoria funkcji rekurencyjnych (której częścią jest arytmetyka) jest powszechnie i efektywnie stosowana w informatyce teoretycznej. Niezależnie od oceny jego merytorycznej trafności (nie wypowiadam się na temat zdania o owej powszechności, bo nic o tym nie wiem; czy Jarek mógłby tę informację potwierdzić?) uparcie – choć na różne sposoby – powtarzam, że taki argument jest akurat w naszej dyskusji bezwartościowy. Powód jest prosty: matematyczne pojęcie „funkcji rekurencyjnej” jest zakresowo równoważne z informatycznym (i teoretycznie lepszym, jeśli wierzyć opinii np. K. Goedla) pojęciem „funkcji obliczalnej za pomocą maszyny Turinga”. NIE JEST więc KONIECZNE posługiwanie się matematyczną wersją teorii obliczalności; wystarcza – w pewnym sensie prostsza – jej wersja informatyczna („turingowska”). W konsekwencji: jeśli teoria funkcji rekurencyjnych jest jedynym „siedliskiem” liczb w informatyce, to liczby w informatyce nie są konieczne. Co było do udowodnienia. [Czy gdzieś popełniłem błąd? Jeśli tak, to w którym kroku rozumowania?]
Jeśli się nie mylę i argument „ze stosowania w informatyce teorii funkcji rekurencyjnych” jest jedynym argumentem za NAwI, to teza ta nie ma kompletnie żadnego wsparcia.
Będę bronił uprawiania informatyki w duchu Turinga. To właśnie Turing był prekursorem myśli, by pozbyć się liczb z zestawu narzędzi służących poznaniu. Wyjaśnię, że nie chodzi o zanegowanie konceptu liczby-indywiduum – w informatyce dalej korzystamy z pojęć takich jak „całkowita liczba 5”, „niewymierna liczba π”, „2048 cyfr rozwinięcia dziesiętnego obliczalnej liczby ε”, a także z ograniczonych zbiorów liczb.
W opisie swojej maszyny Turing postawił warunek, by zbiór dostępnych symboli miał moc N, a zbiór stanów maszyny moc M, gdzie wartości N i M są dowolne, ale koniecznie skończone. Taśma maszyny ma wprawdzie nieskończoną długość, ale tylko po to, by nie było tłumaczeń w stylu Jasia z IIIb – „nie mogę pokazać zadanych do domu na dzisiaj słupków, bo pies Alefik zjadł mój zeszyt w kratkę”. Po skończeniu obliczeń i zatrzymaniu się maszyny zawsze zostaje nieskończona ilość nieużywanej taśmy.
Nie ma zatem obowiązku, by maszyna Turinga była maszyną pracującą w kodzie binarnym (może być siódemkowy), ale też nie może być tak, że dopuścimy wszystkie liczby naturalne jako jej symbole.
Co by było, gdyby warunku skończoności nie było, gdyby maszyna liczyła po prostu na liczbach
naturalnych? Zdaje się, że są zwolennicy takiego podejścia – im być może się wydaje, że Turing o tej ograniczoności napisał, bo miał zły dzień, a ona tylko przeszkadza. Zatem proszę, śmiało – jakie wartości poznawcze niesie ze sobą koncept maszyny potrafiącej „by design” robić wszystko z liczbami naturalnymi? Dlaczego nikt tego konceptu nie rozwija?
Ja oczywiście chciałbym mieć na biurku taką maszynę, bo to potężne i praktyczne narzędzie. Najlepiej obok samonakrywającego się stoliczka i zaczarowanego ołówka. Pasuje ona do świata bajek, ale nie do świat nauki.
Jarek
PS:
Jakieś „przyspieszające maszyny Turinga”? – do działu fantastyki nienaukowej windą na trzecie piętro, ostatnie drzwi w korytarzu. Gdybyśmy dzisiaj dysponowali maszyną Turinga przyspieszoną od samego początku do fizycznych granic możliwości, czyli jeden krok w najkrótszym ze znanych fizyce kwantowej okresów, ale wciąż jednotaśmowej (i dajmy na to aż 2048-bitowej) – to ona i tak nie wygra z zespołowym wysiłkiem współczesnych komputerów.
Sytuacja polemiczna faktycznie ulega zmianom i tezy słabną — tak jak napisał Harry. Jarek docenia informatyczną użyteczność liczb-indywiduów, a Harry „odpuszcza” teorię konkatenacji na rzecz Turingowskiego modelu obliczeń (który jest równoważny mod. f. rekurencyjnych).
Wydaje mi się także, że wszyscy bez wyjątku nie tyle bronimy kategorycznie swoich tez, co próbujemy dobrze uzasadnić pewne przypuszczenia. Tutaj też zgadzam się z Harrym.
Co do niezbędności (a na pewno: wielkiej użyteczności) kategorii liczby w analizie ograniczeń mod. Turinga, to podtrzymuję moją – przydługą być może – wypowiedź z dn. 20.12 (g. 21.04), pod nr II. Wypowiedź dotyczy co najmniej metodologii inf., która też wchodzi w zakres dyskusji (zgodnie z jej tytułem).
Co do odparcia mojej arg. [1] – [4] przez Harry’ego, to muszę zauważyć, że pominął on dyskretnie problem obl. analogowych i rekurencyjnych f. rzeczywistych (w swoich pracach pisze o tym modelu J. Mycka). Sam Jarek zresztą napisał w innym miejscu, że: „do zajmowania się komputerami analogowymi wciąż wystarcza poczciwa analiza matematyczna.” (Podstawą analizy mat. jest def. liczb rzeczywistych.).
Co do niesk. taśmy w mod. Turinga (liczba jej klatek ma moc alef zero), to jest to szerszy temat. Nie kwitowałbym go jednak dowcipem o Jasiu. Moim zdaniem, niesk. taśma ma głęboki sens, bo czyni z MT obiekt idealny – który można odnieść do wszystkich realnych komputerów cyfr. o dowolnie dużych zasobach pamięciowych (dowolnie wzmacnianych w przyszłości). Niesk. taśma jest również istotna w dowodzie Turinga o istnieniu liczb nieobliczalnych, a tym samym problemów nieobliczalnych, bo pozwala ustawić kolejne maszyny w niesk. przeliczalny ciąg. Ale to temat na szerszą analizę. W ogóle kwestii nieskończoności w informatyce nie ignorowałbym.
Koniec końców moje przypuszczenie o niezb. kategorii liczby w inf. i jej metodologii traktuję nadal jako nieźle uzasadnione. Choć nie będę się go kurczowo trzymał…
Swoją drogą ciekaw jestem, jakiego kandydata/tkę na niezbędną dla informatyki kategorię matematyczną zaproponowałby Harry.
W kontekście szeregowania maszyn na potrzeby dowodu jest tak, jak w „dowcipie o Jasiu”. Turing układa po kolei maszyny w ich stanie początkowym, czyli te, które już zawierają program, ale wyników obliczeń jeszcze nie. Wymagania co do programu są takie, że musi mieć skończoną długość. Taśma nieskończonej długości wynika tylko z Jasiowych potrzeb (które w nieco innym ujęciu przedstawiam w komentarzu obok).
Nie wiem, czy to coś wniesie, ale sprostuję…
W przekątniowym dowodzie Turinga (dow. istnienia liczb nieobliczalnych) mamy dwa szeregi: 1) szereg maszyn z początkową zaw. taśmy (jest to nieskończony szereg maszyn uporządkowanych zgodnie z ich rosnącymi numerami, które to numery są efektem jednoznacznego przypisania zawartościom taśm pewnych liczb), 2) szereg wyników obliczeń, czyli końcowych zawartości taśm kolejnych maszyn z szeregu (nie musimy ich dokładnie znać, ale wiemy, że jakieś są i to one odgrywają kluczową rolę w dowodzie). Owe końcowe zawartości taśm czyli wyniki obliczeń (u Turinga chodzi o sekwencje cyfr ze zbioru {0,…9}) wyznaczają jednoznacznie wszelkie możliwe liczby obliczalne.
O tym,że istnieją liczby nieobliczalne, upewnia nas pytanie o to, czy którakolwiek z maszyn zestawionych na liście 1) może wygenerować pewien szczególny ciąg C powstający przez zmianę n-tej cyfry w n-tej sekwencji i zestawienie wyników tych zmian własnie w ciągu C. Okazuje się,że ciągu takiego nie może być w szeregu 2), a zatem nie może on pochodzić od żadnej z maszyn, a zatem odpowiada on liczbie nieobliczalnej.
Pominąłem wiele szczegółów, ale idea jest taka jak wyżej.
Chodziło mi tylko o to, że w dowodzie Turinga wyniki obliczeń są bardzo ważne (a nie tylko początkowe zawartości taśm kolejnych maszyn)
(A) Wbrew ostatniej opinii Pawła, nie odpuszczam sobie teorii konkatenacji. Została ona w dyskusji przytoczona wyłącznie po to, żeby pokazać, że w metodologii (formalnej) można niekiedy skutecznie posługiwać się pojęciem rozstrzygalności (a więc też obliczalości) bez potrzeby korzystania z arytmetyki. W szczególności można podać taką (konkatenacyjną) wersję dowodu twierdzenia Goedla, w której nie używa się arytmetyki. Ten fakt, choć osłabia ogólne przekonanie o niezbędności arytmetyki w rozważaniach metateoretycznych, nigdy nie był używany przeze mnie jako decydujący argument w tej dyskusji. Mój główny argument jest inny. Powtórzę go jeszcze raz, w nieco ogólniejszej wersji: podawane dotąd przez Pawła i Poliandra przykłady użycia pojęć arytmetycznych w rozwiązywaniu zagadnień informatycznych są „niekonieczne” w tym sensie, że można je zastąpić przykładami niearytmetycznymi lub wyjaśnić w kategoriach niearytmetycznych. W szczególności arytmetyczne pojęcie „funkcji rekurencyjnej” jest niekonieczne, gdyż można je zastąpić niearytmetycznym (i zarazem typowo informatycznym) pojęciem „funkcji obliczalnej za pomocą maszyny Turinga”.
(B) Bronię tu kategorycznie metatezy (a nie meta-przypuszczenia), głoszącej, iż nikt w tej dyskusji nie wskazał jeszcze żadnego dobrego argumentu za NAwI. Jeśli taki argument istnieje, to prosiłbym o jego jasne i wyraźne wskazanie. Moje oczekiwanie jest w tej sytuacji zupełnie podstawowe: chodzi o podanie przykładu takiego użycia arytmetyki w rozwiązywaniu typowego/ważnego problemu informatycznego, którego nie da się zastąpić równoważnym użyciem teorii niearytmetycznej. Ja naprawdę nie wykluczam tego, że takie przykłady istnieją. I sam jestem ciekaw, czy one istnieją. Istnieją?
(C) W swoim rozumowaniu nie pominąłem kwestii obliczeń analogowych. Po prostu przyjąłem jako ustalone podane we wcześniejszej fazie dyskusji wyjaśnienie, że takie obliczenia można opisać jako obliczenia automatów nieskończenie (czy też nieprzeliczalnie) stanowych. To przecież nie jest wyjaśnienie w kategoriach arytmetycznych. Poza tym oczekuję, że ewentualne przykłady niezbywalnych zastosowań arytmetyki w informatyce będą dotyczyły przede wszystkim „informatyki” we współczesnym znaczeniu tego słowa (a więc informatyki standardowej, „turingowsko-podobnej”). Dzięki temu być może zminimalizujemy ryzyko zaliczenia przedmiotów naszych rozważań do kategorii samonakrywających się stoliczków i zaczarowanych ołówków.
(B) Istnieją?
Nie istnieją. Istnieją za to dowody na to, że jest odwrotnie. Najbardziej zręczny dowód skonstruował Alan Turing, został on później nazwany „maszyną Turinga”.
Maszyna nie musi posługiwać się liczbami, wystarczy jej skończony zbiór symboli. Tym bardziej arytmetyka może być jej całkiem obca. Mimo tak dużych ograniczeń i wielkiej prostoty, maszyna potrafi zmierzyć się z tak złożonymi problemami, że się w głowie nie mieszczą. No, powiedzmy, że w głowicy – maszyna ma nie głowę, lecz głowicę. Problem opisany jest symbolicznie jako program na taśmie. Program wprawdzie musi być skończony, ale nie ma ograniczeń na jego długość. Maszyna nie jest w stanie przeczytać całości i zastanowić się nad jego analizą (myślę, że odrobina antropomorfizacji niczego nie ujmuje opisowi) – na to nie pozwalają ograniczenia liczby stanów głowicy. Musi realizować krok po kroku, zapominając od razu co było przed chwila i nie wiedząc co jej każą robić za moment. Podobnie jest z wynikami tych działań. Zapisywane są na dalszym odcinku taśmy, tu nawet nie ma ograniczeń (innych niż czasowe) co do długości tego zapisu. Jeśli zamysłem algorytmu jest zapisanie rozwinięcia jakiejś liczby, to zapisywane są jej kolejne cyfry (dziesiętne, binarne, jeszcze inne), a nie po prostu liczba, której ani algorytm, ani maszyna „nie ogarnia”. Nic z tego, że Turing dał też możliwość czytania z taśmy zapisanych wcześniej wyników. Maszyna może wrócić do początku swojego zapisu i przesuwając się dalej czytać bezrefleksyjnie kolejne symbole. Ale i tak nic z tego nie zrozumie.
Do wyników działania maszyny Turinga dobrze pasuje określenie „liczby syntetyczne”. Są identyczne z pozostałymi liczbami, ale nie powstały w wyniku atomowych operacji arytmetyki, lecz stworzył je wielokrokowy algorytm. (Termin „operacje atomowe” jest często używany w informatyce – oznacza działania, które zawsze wykonywane są w całości jako jedność, a dokładniej nie mogą być efektywnie przerwane w wyniku błędu wykonywania programu. Albo wszystko pójdzie zgodnie z planem, albo nie stanie się nic).
1.
Chodzi o podanie przykładu takiego użycia arytmetyki w rozwiązywaniu typowego/ważnego problemu informatycznego, którego nie da się zastąpić równoważnym użyciem teorii niearytmetycznej. Ja naprawdę nie wykluczam tego, że takie przykłady istnieją. I sam jestem ciekaw, czy one istnieją. Istnieją?
Nie jest to może przykład praktyczny, ale [Mycka & Piekarz] piszą tak (w razie czego podam namiary):
Twierdzenie 4 gwarantuje nam, że dzięki rzeczywistym funkcjom rekurencyjnym problem stopu jest problemem rozstrzygalnym. Zatem model rzeczywistych funkcji rekurencyjnych jest mocniejszy niż klasyczne modele obliczalności.
Nie wchodzę tu w kwestię fizycznej realizowalności obl. analog. Trzymam jednak Jarka za słowo, że do ich opisu stosuje się świetnie stara poczciwa analiza (jej podstawą jest arytm. liczb rzeczywistych)
2.
„liczby syntetyczne”. Są identyczne z pozostałymi liczbami, ale nie powstały w wyniku atomowych operacji arytmetyki, lecz stworzył je wielokrokowy algorytm.
Może się czepiam, ale czy ów wielokrokowy algorytm, jeśli go przełożyć na język funkcji rekurencyjnych, nie jest po prostu wielokrotnym zastosowaniem tych funkcji (które odwołują się do atomowych operacji arytm.)
Przykład Mycki i Piekarz jest chyba wzięty spoza standardowej informatyki? Czy model obliczeń związany z rzeczywistymi funkcjami rekurencyjnymi posiada fizyczną realizację? Jeśli nie, to czy nie wchodzimy w strefę dyskursu o urządzeniach typu „zaczarowany ołówek”? Jeśli nie, to czy arytmetyczne pojęcie „rzeczywistej funkcji rekurencyjnej” nie da się zastąpić równoważnym, niearytmetycznym pojęciem „funkcji obliczalnej za pomocą automatu nieskończenie stanowego”? Za dużo pytań, aby przyjąć wskazany przez Pawła przykład jako przykład jasnego i wyraźnego użycia arytmetyki w informatyce, którego nie da się zastąpić użyciem jakiejkolwiek teorii niearytmetycznej.
1. Przy robocie z maszynami analogowymi faktycznie wystarczała poczciwa analiza matematyczna, ale dzisiaj nikt już tym tematem się nie zajmuje. Ja natomiast nie zajmuję się niepraktycznymi i nierealnymi modelami, więc trudno mi cokolwiek powiedzieć na temat podanego przykładu.
2. Zdecydowanie tak nie jest, że pomysł Turinga dotyczy tylko mechanizacji („machinizacji”?) arytmetyki.
3. (Z tego wątku, w którym WordPress nadmiernie zawęził nam horyzont dyskusji). Wnosi to niewiele. W dowodzie przekątniowym Turinga mamy dwa ciągi, nie szeregi – co ze względu na ścisłość terminologii matematycznej warto sprostować. Ten drugi ciąg jest zwykłym ciągiem złożonym ze zwykłych liczb odczytanych z taśm, sama koncepcja budowy maszyny nie jest w tym momencie już istotna. Natomiast bardzo istotne jest to, że gdyby maszyna znała pojęcie liczb i arytmetyki, to nieskończona taśma w ogóle nie byłaby potrzebna. Wynik obliczeń dałoby się przechowywać w jednej komórce, modyfikowanej przez algorytm w każdym kroku.
To ja też troszkę popociągam za słówka :)
Ad 1)
„Nikt już tematem się nie zajmuje”.
Mocno powiedziane: modelami obliczeń analogowych, a ogólniej hiperobliczeń, zajmuje się całkiem wiele osób — mnie to np. bardzo interesuje (i w swoich tekstach metodologicznych drażę ten temat; zresztą sam mi pomogłeś parę rzeczy kiedyś zrozumieć, za co dziękuję). Uważam,że szeroko pojęta informatyka (a o takiej dyskutujemy) zajmuje się tą tematyką.
'Niepraktyczne i nierealne modele”.
Też mocno powiedziane.
Model obliczeń turingowskich też byłby w pewnym sensie niepraktyczny, gdyby dysponowano tylko technologią mechaniczną, a nie elektroniczną (jak w czasach Babbage’a)
Modele obliczeń kwantowych też można byłoby uznać za całkowicie nierealne, gdyby nie odkryto pewnych zjawisk w mikro-świecie.
Uważam nawet, że obowiązkiem filozofa jest zajmowanie się kwestiami nie do końca realnymi i praktycznymi… Może w ten sposób wprowadzić do nauki lub wzmocnić w nauce pewne idee.
Ad 2.
Ale czy zdefiniowane przez Turinga liczby obliczalne (to do nich redukują się programy i wyniki maszyn Turinga) nie muszą spełniać pewnych warunków, które narzuca arytmetyka (de facto liczb naturalnych), a tym samym maszyny Turinga (i słabsze od nich realne komputery cyfrowe) nie muszą podlegać pewnym ograniczeniom?
Ad 3.
Użyłem sformułowania szereg, bo Ty w swoim komentarzu mówiłeś o szeregowaniu maszyn (Ale faktycznie trzymając się matematycznych rozróżnień, chodzi o ciągi).
Koncepcja budowy czy też ogólne zasady działania MT jest istotna, bo w rzeczonym dowodzie chodzi o maszyny Turinga wlaśnie (idealne komp. cyfrowe), a nie inne maszyny (np. analogowe).
Ostatnie dwa zdania punktu 3 warto byłoby rozwinąć (nawet w formie osobnego wpisu). Nie za bardzo je rozumiem.
Mam taką wstępną refleksję:
Znać pojęcie liczby — to również wiedzieć,że pojecie to ma zastosowanie do nieskończonej liczby przypadków (np. pojęcie dwójki ma zast. do niesk. mnogości par). Człowiekowi jest zatem potrzebne jakieś 'czucie nieskończoności’. A więc maszynie, która mogłaby znać pojęcie liczby, byłby potrzebny jakiś element infinitystyczny. Nie mówię,że jest nim niesk. taśma MT, ale wydaje się, że same układy skończone nie pomogą.
Pozdrawiam już prawie noworocznie!
(1) Nikt nie zajmuje się konstrukcją komputerów analogowych. To, czemu kiedyś służył zestaw „Mały Konstruktor” złożony z gromadki wzmacniaczy operacyjnych, potencjometrów, baterii przełączanych kondensatorów i szuflady na kable i kabelki, dzisiaj robi komputer… no, chciałoby się powiedzieć „cyfrowy”, ale nie o „symulacje numeryczne” tu chodzi. Obliczenia symboliczne to też ważna dziedzina informatyki. Współczesne programy w okamgnieniu potrafią przekształcić i rozwiązać tyle równań różniczkowych, ile studenci wszystkich politechnik świata zebrani na jednym wielkim kolokwium. Pół wieku temu zakładano, że komputery nadają się tylko do liczenia. A tu w ogóle pojęcie liczby nie występuje.
Wielką krzywdą dla Turinga jest postrzeganie go jako „wynalazcy komputera”, który tylko dlatego klecił go niczym Adam Słodowy ze skrawków papieru, starej szprychy rowerowej i niepotrzebnej już w domu szpulki od nici, bo nie miał dostępu do lamp. Jego wkład to coś znacznie więcej.
(2) Ograniczenia maszyny są mocniejsze od ograniczeń „produkowanych” wyników (choć są to ograniczenia różnego rodzaju i porównanie jest nieco subiektywne). To stanowi o wartości modelu. Gdyby było odwrotnie, nie byłby tak atrakcyjny.
(3) Całkiem dobry pomysł (z rozwinięciem w formie wpisu).
Zdaje sie, że:
1.mianem 'liczb…’ (choćby 'liczb informatycznych’) mogą być nazywane 'byty’ przez praktycznych Informatyków definiowane/konstruowane- na co pozwala tolerancyjna w przydawaniu określenia 'liczby …’ matematyka, jak i szeroki (filozoficzny) ogląd 'liczb’ istoty.(Wyznaczony w „rozgrywce” idealistycznych intuicji i pragmatycznych pożytków szczegółowych idej liczby zastosowań: wszak określano mianem 'liczb …”coraz to nowe obiekty- idealne byty, określone wyabstrachowanymi relacjami, pozwalające porzadkować/przeliczać/mierzyć…)
1.1.Innymi słowy: nie istnieje ograniczenie dla tej 'liczb…’ twórczości co do tego jakie aksjomaty służące definicji 'liczb (informatyczmych)’ konstrukcji, ani co do do warunków jakie utworzone za ich pomocą zbiory miały by spełniać takie, że 'obiekty’ informatyczne nie powinny być określane mianem 'liczb’- że lepiej pasuje do nich pojęcie X. (W szczególności np. mała moc zbioru 'liczb informatycznych’, ani to, że cześć aksjomatów określajacych 'informatyczne liczby’ wynika z (wybranych) fizycznych własności informatycznego tworzywa/hardware’u, nie sprawiają, że miano 'liczby’ w odniesieniu do nich staje się mniej trafne/użyteczne niż jakiekolwiek inne).
2.Arytmetyka (w ogólności) definiuje się poprzez zbiór zasad (abstrakcyjnych) działań na liczbach. W szczegolności to, że jakiś zbiór idealnych operacji na obiektach, które najwygodniej (bo możemy wykorzystywać cześć schematow przekształceń przećwiczony przez mayematykę) nam nazwać 'liczbami …’ trafniej będzie opisywał możliwości Informatyki niż arytmetyka Peano, nie sprawi, że 'arytmetyka’ (choćby informatyczna)’ nie będzie jego dobrym określeniem.
2.1.Możliwość zapożyczenia schematów postępowania najlepiej przećwiczonych/przemyślanych w (poza-informatycznej) matematyce sprawia, że trudno chyba pożucić by było takie rozumienie (w idealnym powiązaniu z matematyką i w pewnej abstrakcji od wszystkiego co poza nimi) informatycznych fenomenów i regół postępowania z nimi.
3.Zatem jeśli istnieje pomysł na jakiś nowy, lepszy porządek (tak wyraźne rozdzielenie informatyki i matematyki, że 'liczby …’ i 'Arytmetyka…’ przestaną być trafnym mianem w odniesieniu do „zjawisk” Informatyki) to proszę o jego przedstawienie.
3.1.Obawiam się jednak, że będzie konieczna zmiana rozumienia (filozoficznego i matematycznego) 'liczb’ czy 'Arytmetyki’ bo inaczej matematycy mogą uparcie (tolerancyjnie) włączać twory takiego nowego królestwa do swego dominium.
Chciałbym tylko zwrócić uwagę dyskutantów, że w innym miejscu pojawił się kolejny głos w naszej dyskusji.
Mianowicie w ramach wpisu pt. „O różnych sposobach istnienia i nieistnienia liczb
Rozmyślanie noworoczne” Witold Marciszewski dopisał fragment odnoszący się wprost do powyższej dyskusji.
Podaję adres: http://marciszewski.eu/?p=10058.
Dyskusję możemy kontynuować tutaj lub pod w/w wpisem.