Marek Hetmański - Maszyna Turinga a umysł ludzki.pdf - Logika - abi77

Tytuł: Maszyna Turinga a umysł ludzki

Autor: Marek Hetmański / hetman@ramzes.umcs.lublin.pl

Źródło: http://www.kognitywistyka.net / mjkasperski@kognitywistyka.net

Data publikacji: 09 VIII 2002

Termin ‘maszyna Turinga’ odnosi si ę do teoretycznego projektu maszyny matematycznej

sformułowanego w latach trzydziestych przez Alana M. Turinga. Jest on szeroko

wykorzystywany i dyskutowany tak Ŝ e poza matematyk ą w psychologii poznawczej, teoriach

sztucznej inteligencji, jest podstaw ą tzw. komputacyjnej koncepcji umysłu. Zamiarem

artykułu jest analiza teoretycznej tre ś ci maszyny Turinga (pewnych jej ogranicze ń ) oraz ocena

u Ŝ yteczno ś ci tego poj ę cia w psychologicznych i filozoficznych koncepcjach ludzkiego

umysłu. Teza jest nast ę puj ą ca – maszyna Turinga nie mo Ŝ e by ć wła ś ciwym (poprawnym)

modelem umysłu i działania ludzkiego; mo Ŝ e by ć niemniej u Ŝ yteczna (w ograniczonym

zakresie) w analizie niektórych czynno ś ci poznawczych człowieka. Kwesti ą otwart ą jest to,

jakie inne jeszcze modele mog ą by ć pomocne w opisie poszczególnych rodzajów my ś lenia i

działania człowieka; czy inne rodzaje maszyn (np. homeostat cybernetyczny, sieci

neuronowe, uniwersalny komputer kwantowy, czy inne rodzaje maszyn analogowych) mog ą

symulowa ć cało ść (mo Ŝ e tylko jaki ś aspekt) działa ń człowieka?

1. Problem rozstrzygalno ś ci w matematyce.

Rozstrzygalno ść a algorytmizacja

Algebraizacja logiki przeprowadzona przez Boole'a, rozwini ę ta potem przez wielu innych

autorów, doprowadziła w latach dwudziestych i trzydziestych obecnego stulecia do bada ń nad

podstawami matematyki. W ich ramach postawiono szereg wa Ŝ kich kwestii, równie Ŝ takie,

które maj ą teoriopoznawcze znaczenie i s ą dyskutowane poza matematyk ą . Jedn ą z nich jest

problem rozstrzygalno ś ci . Jest to problem takiej własno ś ci aksjomatycznych systemów, która

polega na tym, Ŝ e w wi ę kszo ś ci przypadków mo Ŝ na poda ć warunki ich obliczalno ś ci przez

zastosowanie funkcji rekurencyjnych (funkcji obliczalnych). Funkcje takie w sko ń czonej

liczbie kroków podaj ą warunki rozstrzygni ę cia tego, czy dane twierdzenie jest elementem

systemu, czy metoda tego rozstrzygni ę cia jest efektywna. Efektywna metoda jest

algorytmem .

Zagadnienie rozstrzygalno ś ci podj ą ł Turing w swojej koncepcji maszyny matematycznej.

Chc ą c poda ć warunki obliczalno ś ci, efektywnego rozwi ą zania danego zadania

matematycznego sformułował abstrakcyjne, czysto teoretyczne poj ę cie automatu, który

samoczynnie wykonuje pewne proste operacje na symbolach w celu podania rozwi ą zania tego

zadania. Automat ten wykonuje swoje operacje analogicznie do działa ń ka Ŝ dego rachmistrza

wykonuj ą cego proste czynno ś ci rachunkowe, jak zapisywanie danych liczbowych i

M. HETMA Ń SKI, Maszyna Turinga a umysł ludzki

po ś rednich wyników, posługiwanie si ę okre ś lonymi symbolami i regułami, dochodzenie do

rozwi ą zania zadania. Wst ę pnym zamiarem Turinga było wykazanie, Ŝ e wszelkie efektywnie

rozwi ą zywalne (obliczalne, algorytmizowalne) zadanie matematyczne mo Ŝ e by ć wykonane

przez taki automat.

Podstawowym sformułowaniem maszyny matematycznej do podawania warunków

rozstrzygalno ś ci zagadnie ń matematycznych jest artykuł Turinga z 1936/37 roku pt. On

Computable Numbers with an Application to the Entscheidungsproblem . Wyst ą pienie Turinga

zbiegło si ę w czasie i było równorz ę dne co do warto ś ci z osi ą gni ę ciami A. Churcha, E. Posta i

S. Kleene'a; przypisuje si ę mu jednak Ŝ e najwi ę ksz ą rang ę ze wzgl ę du na najwyra ź niej

sformułowane zało Ŝ enie o mo Ŝ liwo ś ci mechanizacji oblicze ń , jak równie Ŝ samo u Ŝ ywanie

słowa ‘maszyna’ (por. Gandy 1988). W swoim artykule Turing odniósł si ę do zagadnienia

(funkcjonowało ono wówczas jeszcze pod niemieck ą nazw ą ) sformułowanego przez Dawida

Hilberta. Wyra Ŝ ało si ę ono w pytaniu czy istnieje pewna ogólna, mechaniczna procedura

rozstrzygania ogólnej klasy poprawnie sformułowanych problemów matematycznych?

Inaczej mówi ą c, czy dla takich zagadnie ń istnieje algorytm podaj ą cy warunki rozwi ą zania

zagadnienia? Oczekiwanie Hilberta, co do mo Ŝ liwo ś ci podania procedur algorytmicznych dla

dowolnego zagadnienia matematycznego (w tym wyra Ŝ ał si ę jego program formalistycznej

interpretacji matematyki) zostało, skrótowo mówi ą c, przez Turinga (podobnie jak przez

innych) zasadniczo podwa Ŝ one. Oryginalnym i wa Ŝ nym jego wkładem w to zadanie jest

podanie istotnych warunków, ale równie Ŝ ogranicze ń , procedur mechanicznych w odniesieniu

do bardzo abstrakcyjnie i szeroko zdefiniowanej klasy maszyn matematycznych. Dzi ę ki

niezwykle sugestywnemu pomysłowi Turinga owocnie zacz ę to rozwa Ŝ a ć nie tylko istotne

kwestie metamatematyczne, ale równie Ŝ konstruowa ć cyfrowe maszyny licz ą ce.

2. Maszyna Turinga – podstawowe zało Ŝ enia

Maszyna Turinga jest tworem wył ą cznie teoretycznym, swoist ą gr ą umysłow ą , konstruktem,

który miał słu Ŝ y ć jego autorowi rozwi ą zaniu wa Ŝ nego metamatematycznego problemu.

Okre ś lenie ‘maszyna Turinga’ wprowadził do u Ŝ ycia po raz pierwszy A. Church w recenzji z

artykułu Turinga. Turinga nie interesowało na samym pocz ą tku rozwa Ŝ a ń , to czy mo Ŝ na

skonstruowa ć fizyczn ą maszyn ę , która dokonałaby algorytmicznych oblicze ń . Dopiero potem

(w trakcie wojny i po niej, gdy brał udział w pracach nad łamaniem szyfrów maszyn

koduj ą cych) zagadnienie to stało si ę dla niego praktyczn ą kwesti ą . W artykule z 1936/37 roku

Turing za punkt wyj ś cia przyj ą ł konstrukcj ę abstrakcyjnego rachmistrza, który dokonuje

oblicze ń z u Ŝ yciem bardzo elementarnych przedmiotów, jak kartki z pokratkowanego zeszytu

do rachunków, na których zapisuje proste znaki na potencjalnie niesko ń czonej ta ś mie.

Postawił przy tym fundamentalne pytanie: „Jakie s ą mo Ŝ liwe procesy, które mog ą by ć

wykonane podczas obliczania?” Miał przy tym na my ś li dosłowne czynno ś ci wykonywane

przez rachmistrza, które mog ą te Ŝ by ć wykonane przez zaprojektowan ą maszyn ę ; u Ŝ ycie

zwrotu ‘mechaniczne wykonanie’ znaczyło w tym kontek ś cie tyle, co „mo Ŝ liwe do

wykonania przez maszyn ę ”. Turing przyj ą ł, Ŝ e czynno ś ci mechanicznego obliczania s ą

ograniczone, podobnie jak ograniczone s ą zmysłowe zdolno ś ci ka Ŝ dego rachmistrza

(obejmuje wzrokiem tylko pewn ą cz ęść kratek na ta ś mie) oraz jego umiej ę tno ś ci umysłowe

(zapami ę tuje pewn ą tylko ilo ść reguł post ę powania podczas obliczania); pod tym wzgl ę dem

istotne matematyczne poj ę cie ma za przesłank ę pewne psychologiczne zało Ŝ enie.

M. HETMA Ń SKI, Maszyna Turinga a umysł ludzki

R. Gandy 1 referuj ą c podstawowe zało Ŝ enia Turinga wprowadził na okre ś lenie ludzkiego

rachmistrza termin ‘komputer’ (w przeciwie ń stwie do ‘komputera’ oznaczaj ą cego fizyczn ą

realizacj ę maszyny matematycznej), którego działanie charakteryzuje si ę :

• liczb ą ró Ŝ nych symboli zapisywanych w kratkach;

• liczb ą przyległych kratek, których tre ść komputer mo Ŝ e rozpatrzy ć (Turing przyj ą ł,

Ŝ e dla rachmistrza czytaj ą cego kratki w układzie linearnym liczba ta jest mniejsza

ni Ŝ 15);

• mo Ŝ liwo ś ci ą zmiany w danym kroku komputera tre ś ci tylko w jednej kratce;

• ilo ś ci ą „stanów umysłu” komputera; jego stan umysłu wraz z tre ś ci ą przegl ą danej

kratki wyznacza działanie komputera i nast ę pny stan jego umysłu; komputer

wykonuje zawsze ustalony, sko ń czony zbiór instrukcji.

Ze wzgl ę du na wymóg pogl ą dowo ś ci maszyn ę Turinga przedstawia si ę równie Ŝ w literaturze

tematu (tak Ŝ e tej popularnej) w mniej lub bardziej fizycznym kształcie graficznych

schematów (ju Ŝ bez psychologicznych implikacji, które czynił sam Turing). Na ich posta ć

maj ą przy tym (co jest zrozumiałe) wpływ elementy z pó ź niejszych technicznych,

konstruktorskich projektów komputera według tzw. architektury von Neumanna. (Wzajemny

wpływ obu matematyków w rozwoju maszyn licz ą cych jest zreszt ą do dzisiaj tematem bada ń

i analiz 2 .

Na tre ść poj ę cia maszyny Turinga składaj ą si ę zatem nast ę puj ą ce elementy, których nie

mo Ŝ na jednak uwa Ŝ a ć w dosłownym znaczeniu za cz ęś ci maszyny 3 :

• jednostka centralna (kontrolna), która okre ś la dowoln ą ilo ść trybów pracy maszyny;

• sko ń czony zbiór nie zmieniaj ą cych si ę w czasie pracy maszyny reguł post ę powania,

dowolnie jednak wymienialny;

• sekwencja klatek w swobodnie przesuwanej ta ś mie, na której maszyna zapisuje/

wymazuje znaki;

• rejestr stanów maszyny (od stanu wyj ś ciowego do stanu ko ń cowego), w ramach

którego realizuje si ę zawsze okre ś lony algorytm przypisany maszynie w danym

zadaniu. Te elementy s ą konieczne, aby móc efektywnie podej ść do zagadnienia

rozstrzygalno ś ci.

Teoretyczne składowe maszyny Turinga przedstawia si ę równie Ŝ (taki jest wymóg

pogl ą dowo ś ci) za pomoc ą pewnej liczby (jej wielko ść zale Ŝ y od stopnia dokładno ś ci opisu)

fizycznych elementów, głównie w nast ę puj ą cych postaciach:

• czytnika;

• ta ś my o nieograniczonej długo ś ci z wyró Ŝ nionymi kratkami, na których mo Ŝ e

znajdowa ć si ę znak, który mo Ŝ e by ć zmieniany w trakcie pracy maszyny; kratka

mo Ŝ e zawiera ć b ą d ź tylko jeden (z co najmniej dwóch wyró Ŝ nionych i

wykluczaj ą cych si ę znaków), b ą d ź by ć pusta; ilo ść znaków stosowanych przez

maszyn ę Turinga mo Ŝ e by ć dowolna, lecz zawsze sko ń czona, przy czym najcz ęś ciej

stosowanym systemem znakowym jest układ binarny: 1 i 0, dzi ę ki któremu maszyna

Turinga ma faktycznie do czynienia z trzema mo Ŝ liwo ś ciami, mo Ŝ e te Ŝ wykonywa ć

operacje równie Ŝ w stosunku do kratki pustej.

Por. R. Ligonniere, Prehistoria i historia komputerów , Ossolineum, Wrocław 1992, ss. 205-214.

M. HETMA Ń SKI, Maszyna Turinga a umysł ludzki

R. Gandy, The Confluence of Ideas in 1936 , s. 81

2 Por. M. Davies, Mathematical Logic and the Origin of Modern Computers , ss. 165-169.

Istot ą działania maszyny Turinga jest etapowe, sekwencyjne wykonywanie kolejnych

podstawowych działa ń . Ka Ŝ de jej działanie okre ś lone jest przez tryb narzucony przez

jednostk ę kontroln ą (stan maszyny) oraz znak odczytywany z ta ś my. W ka Ŝ dym stadium

swojego działania maszyna Turinga mo Ŝ e zatem wykona ć na poszczególnych poziomach

nast ę puj ą ce czynno ś ci:

• na poziomie jednostki kontrolnej przej ść z jednego trybu pracy w drugi lub utrzyma ć

aktualny;

• na poziomie urz ą dzenia zapisu/odczytu w stosunku do danej kratki po jej odczytaniu

maszyna mo Ŝ e: (1) zapisa ć znak, je ś li kratka jest pusta, (2) wykasowa ć znak i

zast ą pi ć go innym znakiem lub pozostawi ć wolne miejsce, (3) nie zmienia ć nic; po

czym mo Ŝ e przej ść o jedn ą kratk ę w lewo lub w prawo, b ą d ź te Ŝ pozosta ć w

miejscu.

Czynno ś ci te układaj ą si ę w list ę (siatk ę ) polece ń , które maszyna ma wykona ć . Sprowadzaj ą

si ę one do działa ń w stosunku do danej kratki (z trzema powy Ŝ szymi mo Ŝ liwo ś ciami),

zachowania lub zmiany stanu maszyny przed kolejn ą operacj ą wobec kratki oraz przesuni ę cia

ta ś my o jedn ą kratk ę w prawo lub lewo. Ilo ść polece ń (instrukcji) jest zawsze sko ń czona,

układaj ą si ę one w list ą , która w cało ś ci determinuje prac ę maszyny. Lista instrukcji danej

maszyny, zapisana na ta ś mie, mo Ŝ e by ć równie Ŝ list ą polece ń dla pewnej innej maszyny

Turinga; jest to wa Ŝ na cecha maszyny zaprojektowanej przez Turinga (o czym pó ź niej)

decyduj ą ca o jej uniwersalno ś ci.

Wszystkie działania wykonywane przez maszyn ę Turinga dyktowane s ą okre ś lonym z góry

programem, na który składaj ą si ę (z funkcjonalnego punktu widzenia) kombinacje trybów

pracy jednostki kontrolnej (okre ś laj ą one jaki rejestr polece ń ma by ć zastosowany) oraz

odczytywanie okre ś lonego znaku. Z mechanicznego punktu widzenia działanie maszyny jest

sekwencj ą dyskretnych przej ść z jednego stanu w drugi i wykonywaniem operacji na znakach

zapisanych na ta ś mie. Maszyna Turinga pracuje przywołuj ą c jedn ą tylko na raz reguł ę ze

sko ń czonego ich zbioru. Odpowiednio do niej operuje znakiem na ta ś mie i odwołuje si ę do

reguły kolejnej a Ŝ do momentu, gdy przywołana reguła nie zatrzyma maszyny. Maszyna

zatem "wie" dwie rzeczy: któr ą reguł ę wykonuje i jakim znakiem z ta ś my operuje. Reguła i

znak determinuj ą jednoznacznie jej sekwencyjne działanie.

Powy Ŝ sz ą , wył ą cznie formaln ą , charakterystyk ę maszyny matematycznej mo Ŝ na uzupełni ć

charakterystyk ą z punktu widzenia teorii informacji. Znaki w kratkach ta ś my mo Ŝ na bowiem

zinterpretowa ć jako informacj ę (dane) a operacje na nich (zamiana znaku jednego na inny)

jako przetwarzanie informacji. Przy zało Ŝ eniu mo Ŝ liwo ś ci dowolnie bogatego słownika

znaków oraz dowolnie zmienianego programu mo Ŝ na powiedzie ć , Ŝ e zasadniczo maszyna

Turinga działa wobec dowolnej informacji ; sposób kodowania informacji (zapis danych)

jest oboj ę tny. W tym poszerzeniu (zbie Ŝ nym z cybernetyk ą ) koncepcji maszyny Turinga le Ŝ y

ź ródło wielu prób u Ŝ ywania jej jako modelu nie tylko matematycznego automatu czy

cyfrowej maszyny licz ą cej (komputera), ale równie Ŝ umysłu człowieka.

3. Uniwersalno ść i ograniczenia maszyny Turinga

Ka Ŝ da maszyna Turinga ma swoj ą okre ś lon ą moc , czyli zdolno ść rozwi ą zywania zło Ŝ onych

zada ń . Jest ona funkcj ą mo Ŝ liwych do przybrania przez ni ą stanów oraz bogactwa słownika,

M. HETMA Ń SKI, Maszyna Turinga a umysł ludzki

czyli przyj ę tych znaków. Maszyny Turinga mo Ŝ na ł ą czy ć (teoretycznie) w dowolne układy.

Dwie maszyny o takiej samej strukturze budowy (ilo ś ci stanów i bogactwie słownika) maj ą

tak ą sam ą moc. Mo Ŝ liwe jest poł ą czenie kilku uzupełniaj ą cych si ę maszyn o ró Ŝ nej

strukturze, lecz przeznaczonych do realizacji jednego okre ś lonego zadania, do wykonywania

bardziej zło Ŝ onych zada ń .

Jest wiele ró Ŝ nych wariantów prostej maszyny Turinga, które mo Ŝ na konstruowa ć poprzez

poszerzanie jej zasadniczych elementów – ta ś my i znaków. W miejsce jednej ta ś my mo Ŝ na

wprowadzi ć wiele ta ś m, równolegle odczytywanych i zmienianych przez urz ą dzenie

odczytu/zapisu. Jednowymiarow ą ta ś m ę mo Ŝ na tak Ŝ e zast ą pi ć dwuwymiarow ą płaszczyzn ą a

nawet trójwymiarow ą przestrzeni ą , co daje o wiele wi ę ksze mo Ŝ liwo ś ci zapisu i odczytu

danych. W pewnym sensie całe otoczenie maszyny Turinga mo Ŝ e by ć potraktowane jako

ta ś ma z zapisanymi znakami. Niemniej jednak ta mo Ŝ liwo ść pozornie tylko poszerza

zdolno ś ci maszyny Turinga, gdy Ŝ w istocie operowanie przez ni ą poszerzon ą i rozbudowan ą

ilo ś ci ą danych i tak sprowadza si ę do operowania w danym momencie znakiem z jednej kratki

jednowymiarowej ta ś my; płaszczyznowe czy przestrzenne uj ę cie danych do przetworzenia

tylko rozbudowuje i wydłu Ŝ a czas operacji. Mo Ŝ liwo ś ci teoretyczne (moc obliczeniowa)

maszyny Turinga nie zale Ŝą od jej parametrów „technicznych”, lecz od zasady działania.

Istotn ą jest w ka Ŝ dym przypadku niesko ń czono ść ta ś my (płaszczyzny czy przestrzeni) z

zapisanymi danymi.

Wariantowo ść dotyczy tak samo drugiego elementu jej budowy – znaków zapisywanych na

kratkach ta ś my. Mo Ŝ e on by ć równie Ŝ dowolnie poszerzany. Tradycyjnie stosowany zapis

binarny (0 i 1) jest o tyle wygodny, Ŝ e odpowiada wa Ŝ nej własno ś ci fizycznej realizacji

(pó ź niejszej w stosunku do projektu) maszyny Turinga w postaci cyfrowego komputera, w

którym impulsy zmiennego pr ą du elektrycznego (wł ą czenie lub wył ą czenie przeł ą cznika w

komputerze lampowym lub niskie i wysokie napi ę cie impulsu w tranzystorze komputerów

nowych generacji) s ą fizycznym podło Ŝ em zapisu dwójkowego. Ma on jednak czysto

konwencjonalne, do pewnego stopnia przypadkowe znaczenie. Mo Ŝ na bowiem zastosowa ć

dowolnie bogatszy, zawsze jednak sko ń czony, zbiór znaków o innej podstawie (dziesi ę tnej,

ósemkowej itp.), który da wi ę ksze mo Ŝ liwo ś ci operowania znakami, lecz mimo tego nie

zmieni to istoty działania maszyny Turinga. Rozszerzony system dwójkowy stosowany w

komputerach cyfrowych pozwala zapisywa ć nie tylko dowoln ą liczb ę naturaln ą , lecz równie Ŝ

liczby ujemne, ułamki. Modyfikacje systemu kodowania pozwalaj ą równie Ŝ na binarny zapis

nie tylko liczb, ale równie Ŝ wzorów matematycznych – algebraicznych, trygonometrycznych,

dzi ę ki czemu odpowiednio skonstruowane maszyny Turinga mog ą wykonywa ć operacje na

wzorach i regułach.

Turing rozwa Ŝ ył mo Ŝ liwo ść poszerzenia mocy maszyny matematycznej. W stosunku do

zwykłych maszyn Turinga wykonuj ą cych proste zadania mo Ŝ na zbudowa ć jedn ą wyró Ŝ nion ą

maszyn ę . Nale Ŝ y list ę (siatk ę ) polece ń , instrukcji dla dowolnej maszyny Turinga zakodowa ć

w postaci ci ą gu symboli 0 i 1 oraz zapisa ć na ta ś mie. Ta ś m ę t ą nast ę pnie trzeba wykorzysta ć

jako pocz ą tkow ą cz ęść danych dla pewnej szczególnej maszyny – nazwanej przez Turinga –

uniwersaln ą maszyn ą , która w stosunku do pozostałych danych z ta ś my działa podobnie, jak

działałaby maszyna zwykła. Skrótowo mówi ą c, uniwersalna maszyna przejmuje jako cz ęść

swojego programu program maszyny zwykłej. Uniwersalna maszyna Turinga potrafi zatem

udawa ć ka Ŝ d ą inn ą dowoln ą maszyn ę Turinga, mo Ŝ e j ą symulowa ć . Wszystkie współczesne

komputery s ą uniwersalnymi maszynami Turinga.

M. HETMA Ń SKI, Maszyna Turinga a umysł ludzki

Marek Hetmański - Maszyna Turinga a umysł ludzki.pdf

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: