\u017ba\u0142uj\u0105c nieco, \u017ce nie mog\u0142em wzi\u0105\u0107 udzia\u0142u w dyskusji seminaryjnej, o kt\u00f3rej mowa w dw\u00f3ch ostatnich wpisach, postanowi\u0142em w\u0142\u0105czy\u0107 si\u0119 do niej post factum, generuj\u0105c w niniejszym blogu co najmniej dwa nowe wpisy. Dodatkow\u0105 zach\u0119t\u0105 by\u0142 fakt, \u017ce podstaw\u0119 dyskusji stanowi\u0142y fragmenty ksi\u0105\u017cki \u201eUmys\u0142\u2013Komputer\u2013\u015awiat \u2026\u201d, kt\u00f3r\u0105 wsp\u00f3\u0142tworzy\u0142em.<\/p>\n
Co to znaczy zatem, \u017ce umys\u0142 jest maszyn\u0105 Turinga?
\nJest to pytanie bardzo wa\u017cne, bo wobec bliskiego zwi\u0105zku mi\u0119dzy maszynami Turinga a komputerami cyfrowymi, idzie w nim o to, jak umys\u0142y ludzkie maj\u0105 si\u0119 do komputer\u00f3w cyfrowych.<\/p>\n
Historycznie rzecz bior\u0105c, maszyny Turinga wymy\u015bli\u0142 angielski matematyk, Alan Turing, kt\u00f3ry za ich pomoc\u0105 obja\u015bni\u0142 \u015bwiatu (w roku 1936) nie do\u015b\u0107 jasne jeszcze poj\u0119cie algorytmu \u2013 algorytmu, czyli procedury mechanicznego przekszta\u0142cania symbolicznych danych w symboliczne wyniki. Przekszta\u0142canie takie wyst\u0119puje nader cz\u0119sto w matematyce, na przyk\u0142ad wtedy, gdy rozwi\u0105zujemy r\u00f3wnania kwadratowe metod\u0105 delty lub dodajemy dwa u\u0142amki o r\u00f3\u017cnych mianownikach (kt\u00f3re to schematyczne czynno\u015bci dobrze znamy ze szko\u0142y).<\/p>\n
Cho\u0107 precyzuj\u0105cy ide\u0119 algorytmu pomys\u0142 Turinga okre\u015bla si\u0119 mianem maszyny, a wi\u0119c czego\u015b fizycznego, to tak naprawd\u0119 \u0142\u0105czy on w sobie dwa znaczenia: hardwarowe czyli sprz\u0119towe, i softwarowe czyli programistyczne.<\/p>\n
Zgodnie ze znaczeniem pierwszym maszyn\u0105 Turinga zwie si\u0119 pewne urz\u0105dzenie fizyczne, wyposa\u017cone w podzielon\u0105 na kom\u00f3rki ta\u015bm\u0119, g\u0142owic\u0119 do odczytu\/zapisu symbolicznych danych oraz fizycznie zrealizowan\u0105 (np. mechanicznie lub elektronicznie) tablic\u0119 instrukcji. Urz\u0105dzenie to dzia\u0142a na podstawie programu zawartego w tablicy instrukcji, przy czym ka\u017cda instrukcja ma posta\u0107 rozkazu warunkowego: \u201eje\u015bli (stanem wewn. maszyny jest x, a g\u0142owica czyta symbol s), to nale\u017cy (zmieni\u0107 stan na y, zmieni\u0107 symbol na p i przesun\u0105\u0107 g\u0142owic\u0119 o jedn\u0105 kom\u00f3rk\u0119 w prawo lub w lewo)\u201d. Wykonuj\u0105c rozkaz po rozkazie, maszyna zmienia zawarto\u015b\u0107 ta\u015bmy, a czyni to dot\u0105d, a\u017c zatrzyma si\u0119 w stanie ko\u0144cowym i pozostawi na ta\u015bmie ci\u0105g symboli b\u0119d\u0105cy zakodowanym wynikiem zleconego jej zadania. Najwa\u017cniejsze jednak, \u017ce maszyna Turinga rozumiana „sprz\u0119towo” wszystko to mo\u017ce robi\u0107 faktycznie; ot tak cho\u0107by jak staro\u015bwiecka i bezpo\u015brednio kontrolowana przez cz\u0142owieka maszyna do pisania.<\/p>\n
Poniewa\u017c kluczowym elementem opisanego mechanizmu jest tablica instrukcji czyli program, to maszyn\u0119 Turinga sytuuje si\u0119 cz\u0119\u015bciej w sferze teorii programowania, a to prowadzi nas do drugiego z wymienionych wy\u017cej znacze\u0144. Przy tym drugim znaczeniu konstrukcja Turinga jest pewn\u0105 ide\u0105 teoretyczn\u0105, kt\u00f3ra pokazuje, na czym polega mechaniczne przetwarzanie danych w wynik, czyli dzia\u0142anie algorytmiczne. Zgodnie z t\u0105\u017ce ide\u0105 dane trzeba w spos\u00f3b jednoznaczny zakodowa\u0107, a potem podda\u0107 \u015bci\u015ble okre\u015blonym przekszta\u0142ceniom, zestawionym jedno po drugim, bez \u017cadnych luk, w programie maszyny. W uj\u0119ciu takim fizyczna konstrukcja maszyny nie ma wi\u0119kszego znaczenia; wa\u017cne, \u017ce dzia\u0142anie automatu jest jako\u015b skorelowane z jego programem (a Turing poda\u0142 po prostu pewien skrajnie prosty i raczej czysto teoretyczny schemat takiej korelacji).<\/p>\n
W tym miejscu trzeba obja\u015bni\u0107 jeszcze jedn\u0105 rzecz.
\nOt\u00f3\u017c Alan Turing wymy\u015bli\u0142 tak naprawd\u0119 dwa rodzaje maszyn. Po pierwsze, by\u0142y to automaty konkretne (o nich traktowa\u0142 tekst wy\u017cej) \u2013 wyposa\u017cone w konkretne programy do wykonywania okre\u015blonych zada\u0144 (np. sumowania liczb).
\nPo drugie jednak, by\u0142y to maszyny uniwersalne \u2013 zaopatrzone w specjalne programy do symulowania dzia\u0142a\u0144 dowolnych automat\u00f3w konkretnych. A co bardzo wa\u017cne: cho\u0107 maszyny drugiego rodzaju mo\u017cna definiowa\u0107 czy te\u017c projektowa\u0107 na r\u00f3\u017cne sposoby (zale\u017cy to m.in. od liczby ich stan\u00f3w wewn\u0119trznych), to poniewa\u017c wszystkie one s\u0105 ze sob\u0105 identyczne pod wzgl\u0119dem mo\u017cliwo\u015bci symulacyjnych, zast\u0119puje si\u0119 je (w sferze matematycznej abstrakcji) zbiorczym poj\u0119ciem jednej jedynej uniwersalnej maszyny Turinga (w skr\u00f3cie: UMT).<\/p>\n
Je\u015bli pomy\u015ble\u0107 o takiej maszynie jako o urz\u0105dzeniu faktycznie dzia\u0142aj\u0105cym, to pracuje ona w spos\u00f3b nast\u0119puj\u0105cy. Na jej ta\u015bm\u0119 wprowadza si\u0119 zakodowany opis pewnego automatu konkretnego M (chodzi g\u0142\u00f3wnie o definiuj\u0105cy go program, czyli tablic\u0119 zmian stan\u00f3w) oraz dane wej\u015bciowe automatu M. Nast\u0119pnie maszyna UMT czyta naprzemiennie: raz dane wej\u015bciowe automatu M, raz jego tablic\u0119 instrukcji (tym w\u0142a\u015bnie steruje jej uniwersalny program) i zale\u017cnie od czytanych w danej chwili instrukcji wypisuje na ta\u015bmie odpowiednie symbole. Poniewa\u017c s\u0105 to takie same symbole, jakie pojawia\u0142yby si\u0119 na ta\u015bmie M-a, o maszynie UMT trzeba stwierdzi\u0107, \u017ce symuluje ona dzia\u0142anie automatu M, kt\u00f3rego program jej dostarczono. A co jest niezwykle wa\u017cne: w taki sam spos\u00f3b mo\u017ce ona na\u015bladowa\u0107 dowolny automat konkretny.<\/p>\n
———<\/p>\n
Cierpliwy czytelnik wpisu zastanawia si\u0119 zapewne, co te wszystkie historyczne automaty \u2013 konkretne, uniwersalne, interpretowane fizykalnie lub teoretycznie itd \u2013 \u0142\u0105czy ze wsp\u00f3\u0142czesno\u015bci\u0105, czyli u\u017cywanymi dzi\u015b komputerami?<\/p>\n
Odpowied\u017a brzmi do\u015b\u0107 zaskakuj\u0105co: ot\u00f3\u017c maszyny Turinga s\u0105 r\u00f3wnowa\u017cne komputerom cyfrowym. Wszystkim. Szybkim i wolnym, istniej\u0105cym i jeszcze nie skonstruowanym.<\/p>\n
W stylistyce programistycznej fakt ten mo\u017cna wys\u0142owi\u0107 nast\u0119puj\u0105co: ka\u017cdy program dla maszyny cyfrowej, niezale\u017cnie od jego stopnia z\u0142o\u017cono\u015bci i wymaga\u0144 co do szybko\u015bci procesora, daje si\u0119 odpowiednio zakodowa\u0107 i powierzy\u0107 do realizacji urz\u0105dzeniu tak prostemu, jakie opisa\u0142 Alan Turing.
\nInnymi s\u0142owy: komputery cyfrowe i maszyny Turinga s\u0105 sobie r\u00f3wnowa\u017cne pod wzgl\u0119dem zakresu mo\u017cliwych do zrealizowania zada\u0144, a wynika to st\u0105d, \u017ce ka\u017cdy program dla maszyny cyfrowej mo\u017cna prze\u0142o\u017cy\u0107 na zestaw instrukcji pewnej maszyny Turinga. Z do\u015b\u0107 oczywistym zastrze\u017ceniem jednak: cho\u0107 zakres rozwi\u0105zywalnych problem\u00f3w jest w obu przypadkach taki sam, to tempo realizacji musi by\u0107 w ka\u017cdym przypadku inne (i w\u0142a\u015bnie zwi\u0119kszaniu tego\u017c tempa s\u0142u\u017cy wci\u0105\u017c dokonuj\u0105cy si\u0119 post\u0119p cyfrowych technologii przetwarzania danych).<\/p>\n
Wr\u00f3\u0107my jednak do turingowskiego rozr\u00f3\u017cnienia maszyn konkretnych i uniwersalnych. W jego \u015bwietle powy\u017csza teza o r\u00f3wnowa\u017cno\u015bci \u201erozdwaja si\u0119\u201d.
\nPo pierwsze bowiem, konkretna maszyna Mi jest r\u00f3wnowa\u017cna komputerowi realizuj\u0105cemu konkretny program (np. program do sumowania liczb); po drugie jednak, uniwersalna maszyna UMT jest r\u00f3wnowa\u017cna nie komputerowi wyposa\u017conemu w takie a takie oprogramowanie, lecz komputerowi przygotowanemu do realizacji r\u00f3\u017cnych mo\u017cliwych program\u00f3w.<\/p>\n
I tak oto dotarli\u015bmy do ko\u0144ca w\u0105tku \u201emaszynowego\u201d, zwie\u0144czonego arcywa\u017cnym obja\u015bnieniem zwi\u0105zku mi\u0119dzy historycznymi pomys\u0142ami Turinga a stosowanymi dzi\u015b powszechnie komputerami cyfrowymi.<\/p>\n
W\u0105tek kolejny \u2013 nazwijmy go \u201eumys\u0142owym\u201d \u2013 podejm\u0119 ju\u017c niebawem, w drugiej cz\u0119\u015bci wpisu, zogniskowanej wok\u00f3\u0142 r\u00f3\u017cnych mo\u017cliwo\u015bci por\u00f3wnywania umys\u0142u z maszynami Turinga (a wi\u0119c i komputerami cyfrowymi).<\/p>\n","protected":false},"excerpt":{"rendered":"
\u017ba\u0142uj\u0105c nieco, \u017ce nie mog\u0142em wzi\u0105\u0107 udzia\u0142u w dyskusji seminaryjnej, o kt\u00f3rej mowa w dw\u00f3ch ostatnich wpisach, postanowi\u0142em w\u0142\u0105czy\u0107 si\u0119 do niej post factum, generuj\u0105c w niniejszym blogu co najmniej dwa nowe wpisy. Dodatkow\u0105 zach\u0119t\u0105 by\u0142 fakt, \u017ce podstaw\u0119 dyskusji … Czytaj dalej