[ Pobierz całość w formacie PDF ]
.Jak się przekonaliśmy, nawet mając do dyspozycji nieskończenie wiele takich maszyn, nie jesteśmy w stanie otrzymać w ten sposób wszystkich liczb, jako że istnieją także liczby nieobliczalne, które nie mogą być wygenerowane w wyniku mechanicznej procedury.Turing zauważył, że w zasadzie nie potrzeba nieskończenie wielu maszyn do wygenerowania takiej listy; wystarczy jedna.Pokazał, iż można zbudować uniwersalną maszynę Turinga, mogącą symulować działanie wszystkich innych maszyn.Możliwość istnienia takiej uniwersalnej maszyny jest dość oczywista.Każdą maszynę można określić przez podanie systematycznej procedury prowadzącej do jej zbudowania, czy to będą maszyny pralnicze, maszyny do szycia, maszyny liczące czy też maszyny Turinga.Podstawowe znaczenie ma tu fakt, że maszyna Turinga sama jest maszyną wykonującą określoną procedurę.Zatem uniwersalnej maszynie Turinga można polecić, aby wpierw odczytywała specyfikację danej maszyny, następnie rekonstruowała zasady jej działania, i ostatecznie wykonywała jej funkcję.Zatem oczywiste jest, że można skonstruować uniwersalną maszynę do wykonywania wszelkich operacji matematycznych.Nie trzeba mieć oddzielnie maszyny dodającej do dodawania, maszyny mnożącej do mnożenia, i tak dalej.Jedna maszyna może robić wszystko.Myśl ta była już zawarta w projekcie Maszyny Analitycznej Babbage'a, lecz trzeba było dopiero upływu prawie stu lat, geniuszu Alana Turinga i potrzeb zrodzonych podczas drugiej wojny światowej, aby koncepcja współczesnego komputera ostatecznie doczekała się realizacji.Może się wydawać zdumiewające, że maszyna, której działanie sprowadza się wyłącznie do odczytywania i zapisywania symboli oraz przesuwania i zatrzymywania taśmy, jest w stanie realizować wszelkie możliwe procedury matematyczne, niezależnie od tego, jak bardzo są abstrakcyjne i skomplikowane.Niemniej jednak przekonanie to, zwane hipotezą Churcha-Turinga, podzielane jest przez większość matematyków.Wynika z niego, że niezależnie od tego, o jaki problem matematyczny chodzi, jeśli nie może on być rozwiązany przez maszynę Turinga, to nie może być rozwiązany w ogóle.Ważną implikacją hipotezy Churcha-Turinga jest to, że szczegóły konstrukcyjne konkretnego komputera są zupełnie nieistotne.Jeśli tylko logiczne zasady jego działania są te same, co w przypadku uniwersalnej maszyny Turinga, wyniki będą zawsze takie same.Innymi słowy, komputery są w stanie wzajemnie symulować swoje działanie.Prawdziwe komputery, którymi się dzisiaj posługujemy, wyposażone są w ekrany, drukarki, plotery, stacje dysków i inne wymyślne urządzenia, jednakże logiczna zasada ich działania nadal odpowiada idei uniwersalnej maszyny Turinga.W połowie lat trzydziestych, gdy Turing prowadził swoje badania, wszystkie te ważne praktyczne zastosowania jego idei były jeszcze sprawą przyszłości.Jemu samemu chodziło przede wszystkim o program Hilberta mechanizacji matematyki, z którym zagadnienie liczb obliczalnych i nieobliczalnych ma bezpośredni związek.Rozważmy (nieskończoną) listę liczb obliczalnych, z których każda generowana jest przez jakąś maszynę Turinga.Wyobraźmy sobie uniwersalną maszynę Turinga, której powierzono zadanie sporządzenia tej samej listy poprzez kolejne symulowanie działania każdej z tych maszyn.Pierwszym krokiem takiej maszyny byłoby odczytanie szczegółów konstrukcyjnych danej maszyny.Rodzi się wtedy od razu pytanie: czy uniwersalna maszyna Turinga jest w stanie rozstrzygnąć na podstawie tych szczegółów, jeszcze przed przeprowadzeniem samych obliczeń, czy dana liczba zostanie faktycznie obliczona, czy też obliczenia zawieszą się w jakimś miejscu? Przez zawieszenie rozumiemy tu, że obliczenia zapętliły się i maszyna nie drukuje żadnego wyniku.Jest to tak zwany „problem zatrzymania” - czy można z góry przewidzieć, na podstawie znajomości szczegółów procedury obliczeniowej, czy maszyna obliczy po kolei wszystkie cyfry danej liczby i zatrzyma się, czy też wpadłszy w pętlę, nie zatrzyma się nigdy.Turing wykazał, że na problem zatrzymania odpowiedź jest zdecydowanie negatywna.Posłużył się przy tym sprytnym rozumowaniem.Przypuśćmy, powiedział, że maszyna uniwersalna jest w stanie rozwiązać problem zatrzymania.Co zatem stanie się, gdy maszyna ta spróbuje symulować samą siebie? W ten sposób znów wróciliśmy do problemu samoreferencji.Jak można tego oczekiwać, rezultatem jest zawieszenie się obliczeń.Usiłując symulować samą siebie, maszyna wpada w stan permanentnej pętli.Tak więc Turing doszedł do niezwykłego wniosku, będącego wariantem twierdzenia Godła o zdaniach nierozstrzygalnych: oto maszyna, która ma sprawdzić, czy dana procedura obliczeniowa nie zawiesi się, sama się zawiesza! W tym przypadku nierozstrzygalność dotyczy samych zdań nieroztrzygalnych: nie ma systematycznego sposobu pozwalającego rozstrzygnąć, czy dane zdanie jest rozstrzygalne czy nierozstrzygalne.Stanowiło to oczywiste zaprzeczenie możliwości zamierzonej przez Hilberta mechanizacji matematyki: twierdzenie, którego prawdziwości ani fałszywości nie sposób udowodnić poprzez systematyczną, ogólną procedurę.Głębokie znaczenie wniosku Turinga zostało obrazowo przedstawione przez Douglasa Hofstadtera: „Matematyka przeniknięta jest na wskroś nierozstrzygalnymi zdaniami, jak kawałek mięsa na stek przerośnięty jest włóknami chrząstki, których nie da się wyciąć bez zniszczenia całego steku”.Dlaczego możliwa jest arytmetyka?Wnioski Turinga zazwyczaj przytacza się w odniesieniu do matematyki i logiki.Niemniej jednak mówią nam one też coś o naturze rzeczywistego świata.W końcu, idea maszyny Turinga oparta jest na naszym intuicyjnym pojmowaniu, czym w ogóle jest maszyna, a rzeczywiste maszyny działają tylko dlatego, że umożliwiają im to prawa fizyki.Ostatnio fizyk teoretyczny z Oxfordu David Deutsch ogłosił tezę, że obliczalność jest właściwie własnością empiryczną, to znaczy zależy w istocie od tego, jaki jest świat, a nie jest wynikiem jakiejś koniecznej prawdy logicznej.„Uzasadnienia, dlaczego możliwe jest - pisze Deutsch - zbudowanie, na przykład, kalkulatorów elektronicznych czy też w ogóle wykonywanie obliczeń w pamięci, nie znajdziemy w obrębie samej matematyki i logiki.Jest to możliwe tylko dlatego, że prawa fizyki są akurat takie, iż dopuszczają istnienie fizycznej realizacji działań arytmetycznych, takich jak dodawanie, odejmowanie i mnożenie.Gdyby tak nie było, te tak znane nam rachunki byłyby funkcjami nieobliczalnymi”.Teza Deutscha jest zaiste frapująca.Operacje arytmetyczne, takie jak liczenie, wydają się nam tak wpisane w naturę rzeczy, że nie możemy wyobrazić sobie świata, w którym nie byłyby one możliwe.Dlaczego tak jest? Sądzę, że odpowiedzi należy doszukiwać się w historii i naturze matematyki.Arytmetyka dotyczyła początkowo czysto praktycznych aspektów życia codziennego, takich jak pilnowanie, by nie zginęły owce ze stada, czy też elementarne rachunki.Jednakże na bazie tych podstawowowych działań dodawania, odejmowania i mnożenia nastąpił tak gwałtowny rozwój idei matematycznych i stały się one tak wyrafinowane, że ludzie stracili z oczu ich skromny praktyczny rodowód.Innymi słowy, matematyka zaczęła żyć swoim własnym życiem.Już w czasach Platona niektórzy filozofowie utrzymywali, że matematyce przysługuje niezależne istnienie.A my tak bardzo przywykliśmy do wykonywania prostych działań arytmetycznych, że z łatwością przychodzi nam wierzyć, iż muszą być one wykonywalne [ Pobierz całość w formacie PDF ]
  • zanotowane.pl
  • doc.pisz.pl
  • pdf.pisz.pl
  • agnieszka90.opx.pl