e-gradiva				Sistemi	Motorola	Omrežja
						SERŠ Maribor

Turingov stroj

Nekaj o Alanu Turingu

Alan Mathison Turing se je rodil 23.6.1912 v Londonu. Prvih 13 let je preživel v Indiji, kjer je njegov oče služil v državni službi. Dokler se oče ni upokojil je Alan s starejšim bratom Johnom živel po raznih domovih. Že zelo mlad je s preprostimi kemijskimi poskusi pokazal zanimanje za znanost. Kasneje, ko se je udejanjal kot raziskovalec, se je uveljavil tudi kot pionir računalniške znanosti. Leta 1928 je začel študirati relativnost, pri tem je tudi zaljubil v Christopherja Marcoma, ki je žal že leta 1930 umrl. Christoperjeva smrt ga je potrla in hkrati spodbudila, da se je udejanjal še za mrtvega fanta. Še nekaj let po Christopherjevi smrti si je Alan dopisoval z njegovo materjo in se spraševal, kako je človeški um vključen v materijo. To vprašanje ga je vodilo na študij fizike dvajsetega stoletja, kjer ga je zanimala povezava kvantne mehanike in njegovega vprašanja o materiji in misli. Ob obisku Marcomovega doma je Turing napisal pismo, kjer pravi da verjame v preživetje duha po smrti.

Leta 1931 je bil sprejet na kraljevsko univerzo v Cambidgeu Tu je tudi spoznal von Neumannovo delo. Zelo ga je zanimalo vprašanje izračunljivosti, zato je raziskoval napravo, ki bi bila zmožna rešiti vse rešljive probleme. Ta naprava se danes imenuje Turingov stroj.

Med drugo svetovno vojno je svoje znanje uveljavljal na oddelku za komunikacije Velike Britanije in poskušal razbiti nemške kode, ki so jih Nemci uporabljali za komunikacijo. To je bila zelo zahtevna naloga, saj je kodiranje opravljal računalnik, ki so ga Nemci zasnovali prav za ta namen. Imenoval se je Enigma. Skupina, v kateri je delal tudi Turing, je odgovorila s Colossusom, enoto, ki je hitro in učinkovito razbila Enigmino kodo. Colossus je bil prvi korak k današnjim digitalnim računalnikom.

Po vojni je Turing služboval v državnemu fizikalnemu laboratoriju, da bi nadaljeval z razvojem računalnika.. Tam je razvijal avtomatski računski stroj. Še preden je z delom končal, se je preselil na Manchestersko univerzo, kjer je začel razvijati "Manchesterski avtomatski digitalni stroj" (MADAM). Verjel je, da bo še pred letom 2000 obstajal stroj, ki bo sposoben nadomestiti človeško umsko delo. Junija leta 1954 je umrl. V današnjem času obravnavamo Turinga kot enega najpomembnejših začetnikov računalništva.

Turingov stroj

Svoj matematični model, danes tako imenovan Turingov stroj, je Alan Turing objavil leta 1936. Turing je neodvisno od Churcha v istem časovnem obdobju reševal problem izračunljivosti. S Churchom sta tudi razvila podobno idejo, z razliko, da lambda račun večini ljudi ni povsem jasen in razumljiv, medtem ko Turingov stroj ni težaven za razumevanje. Glavni ideji Turingovega razmišljanja se glasita:

• Matematična funkcija je izračunljiva, če jo je mogoče v končnem številu korakov izračunati na enem od Turingovih strojev. (Church je postavil ekvivalentno tezo za lambda račun).
• Funkcij je več, kot Turingovih strojev, oziroma obstajajo tudi neizračunljive funkcije.

Vsak Turingov stroj je mogoče na preprost način opisati z uporabo mehaničnih delov kot so trak, bralno-pisalna glava in mehanizem za pomik traku. Vedeti pa moramo, da mehanična, ali sploh kakršnakoli fizična, osnova stroja ni bistvena in je samo sredstvo za lažje razumevanje Turingove ideje, ki je v bistvu postopek za matematično dokazovanje. Rečemo lahko, da je Turingov stroj matematični pojem. Mehanična metafora je bila v pomoč Turingu samemu, ki je bil med drugim tudi eden od pionirjev pri razvoju digitalnih računalnikov.

Vsak Turingov stroj vsebuje naslednje dele:

1. Neskončni trak je neskončen po velikosti. Je enodimenzionalen in razdeljen v zaporedje enakih kvadratkov. Vsak kvadrat je sposoben vsebovati samo en simbol iz končne množice ali pa je prazen. Če je neskončen v dolžino, to pomeni, da vsebuje končno število ne-belih (praznih) kvadratkov. Vsi kvadratki ki ostanejo se predvideva, da so prazni. Očitno je da se lahko število praznih kvadratkov spremeni med izvedbo programa. Trak se uporablja samo za branje in pisanje podatkov (oziramo zankov).
2. Program je zaporedno končno število navodil oziroma ukazov. Program ukaže glavi, kaj naj piše in kam naj se premakne, glede na podatek na traku ter trenutnem stanju programa. Turingov stroj normalno posluša navodila v istem redu, v katerem se pojavljajo. Zaporedje bi bilo lahko prelomljeno z navodili, ki zahtevajo preskok na drugo lokacijo. Ko ni več pravila za kombinacijo stanje/simbol, ki jo Turingov stroj sreča, se bo stroj enostavno ustavil in ne bo izvršil nobenega ukaza več.
3. Bralno-pisalna glava je sklop, ki v vsakem trenutku bere določen kvadratek na traku in opravlja ukaze programa v določenem koraku. Ima končno število stanj. Lahko bere simbol iz traka in temelječ na tem simbolu in trenutnem stanju bo napisala drug simbol čezenj. Bralno-pisalna glava lahko spremeni trenuten položaj, ali pa se premakne na desno ali pa levovzdolž po neskončnem traku. Kaj se zgodi je odvisno od podatka v opazovanem kvadratku v katerem se nahaja bralno-pisalna glava. Začetni vrednost služi kot začetek programa. Začetni vrednost je najbolj na levi strani traku, kjer je na začetku tudi bralno/pisalna (R/W) glava.

Procesor P zna izvesti končno množico ukazov, ki jih lahko opišemo v obliki:

st mi uj sk

kjer smo s s označili stanje procesorja, z m znak pod bralno-pisalno glavo in z u ukaz. Deluje tako, da bo pri trenutnem stanju procesorja st in znaku mi pod bralno-pisalno glavo procesor izvršil ukaz uj in spremenil stanje procesorja v sk. Ukaz uj je lahko eden od naslednjih štirih:

1. u_j =m_j , kar pomeni, da se na trak zapiše znak m_j (ki zamenja dosedanji simbol m_i);
2. u_j = D, kar pomeni, da se bralno-pisalna glava pomakne za en segment na desno, oziroma trak za en segment na levo;
3. u_j = L, kar pomeni, da se bralno-pisalna glava pomakne za en segment na levo, oziroma trak za en segment na desno;
4. u_j = H, kar pomeni, da se stroj ustavi.

Elementi Turingovega stroja so predstavljeni povsem mehansko, da lažje razumemo za kaj gre. V praksi so Turingovi stroji največkrat predstavljeni kot računalniški programi, Turingov stroj pa lahko, podobno kot von Neumannovo arhitekturo, pojmujemo kot model računalnika, ki zna vse, kar je možno vedeti oziroma znati.

Da se Turingov stroj ni uveljavil kot model računalnika, izvira iz njegove počasnosti. Tudi programiranje Turingovega stroja je tako zelo težavno in nerodno, da je tudi povsem enostavne probleme, kot naprimer seštevanje in množenje, zelo težavno izpeljati. Zgradba Turingovega stroja je v osnovi določena enolično. Vsak Turingov stroj ima končno množico simbolov (podatkov), stanj procesorja ter ukazov. Simboli, stanja in ukazi niso določeni niti po obsegu, niti po vsebini, iz česa je moč sklepati, da je Turingovih strojev neskončno mnogo.

Turing pa je dokazal obstoj tudi tako imenovanega univerzalnega Turingovega stroja, ki zna izvesti vsak program, ki je bil napisan za katerikoli Turingov stroj oziroma pri enakih vhodnih podatkih dobimo tudi enak rezultat. Turingov stroj postavlja takšno zahtevo: problem j e rešljiv, če ga je možno izvesti na Turingovem stroju v končnem številu korakov. Turingov stroj ima omejeno število stanj in je v točno enem izmed teh stanj v vsakem trenutku.

Gor     Sistemi     Motorola 68XX      Izračunljivost     Omejitve 

SERŠ Maribor, Strokovna gimnazija, leto: 2004, avtor: Janez Klobasa