Tiuringo mašinos kaip algoritmo savybės. Mintis yra materiali: Alanas Turingas kaip „universalus skaičiuotuvas“ Tiuringo mašinos modelis

21.11.2023

Vienas iš svarbiausių šiuolaikinės informatikos klausimų – ar yra formalus atlikėjas, su kuriuo būtų galima mėgdžioti bet kurį formalų atlikėją. atsakymą į šį klausimą beveik vienu metu gavo du iškilūs mokslininkai – A. Turingas ir E. Postas. Jų pasiūlyti atlikėjai skyrėsi vienas nuo kito, tačiau paaiškėjo, kad jie gali mėgdžioti vienas kitą, o svarbiausia – imituoti bet kurio formalaus atlikėjo kūrybą.

Kas yra formalus vykdytojas? Ką reiškia – vienas formalus atlikėjas imituoja kito formalaus atlikėjo kūrybą? Jei žaidėte kompiuterinius žaidimus, objektai ekrane neabejotinai paklūsta žaidėjo komandoms. Kiekvienas objektas turi galiojančių komandų rinkinį. Tuo pačiu metu pats kompiuteris yra atlikėjas, ir ne virtualus, o tikras. Taip išeina, kad vienas formalus atlikėjas imituoja kito formalaus atlikėjo darbą.

Apsvarstykite Tiuringo mašinos veikimą.

Tiuringo mašina yra begalinė juosta, padalinta į ląsteles ir vežimėlį (skaitymo ir spausdinimo įrenginį), kuris juda juosta.

Taigi Tiuringo mašina formaliai apibūdinama dviejų abėcėlių rinkiniu:

A=(a1, a2, a3, …, an) – išorinė abėcėlė, naudojama šaltinio duomenims įrašyti

Q=(q1, q2, q3,…, qm) - vidinė abėcėlė, apibūdina skaitymo-spausdinimo įrenginio būsenų rinkinį.

Kiekviename juostos langelyje gali būti simbolis iš išorinės abėcėlės A = (a0,a1,…,an) (mūsų atveju A=(0, 1))

Leidžiami Tiuringo mašinos veiksmai:

1) įrašyti bet kurį išorinės abėcėlės simbolį į juostos langelį (simbolis, kuris buvo anksčiau, yra perrašytas)

2) pereiti į gretimą langelį

3) pakeiskite būseną į vieną iš tų, kurias rodo vidinis abėcėlės simbolis Q

Tiuringo mašina yra automatas, valdomas stalu.

Lentelės eilutės atitinka pasirinktos abėcėlės A simbolius, o stulpeliai – mašinos būsenas Q = (q0,q1,…,qm). Veikimo pradžioje Tiuringo mašina yra būsenoje q1. Būsena q0 yra galutinė būsena; į ją patekusi mašina baigia veikti.

Kiekviename lentelės langelyje, atitinkančiame tam tikrą simbolį ai ir tam tikrą būseną qj, yra komanda, susidedanti iš trijų dalių
· simbolis iš abėcėlės A
· judėjimo kryptis: „>“ (dešinė), „<» (влево) или «.» (на месте)
· nauja mašinos būklė

Aukščiau pateiktoje lentelėje abėcėlė A =(0, 1, _) (yra 3 simboliai) ir vidinė abėcėlė Q=(q1, q2, q3, q4, q0), q0 yra būsena, dėl kurios vežimas sustoja.

Panagrinėkime keletą problemų sprendimo būdų. Turingo mašiną galite atsisiųsti svetainės skiltyje.

1 uždavinys. Tegu A=(0, 1, _). Juostelės langeliuose yra abėcėlės simboliai tokia tvarka: 0011011. Vežimas yra virš pirmojo simbolio. Būtina sukurti programą, kuri pakeistų 0 į 1, 1 į 0 ir grąžintų vežimėlį į pradinę padėtį.

Dabar apibrėžkime vežimo būsenas. Aš juos vadinu „vežti troškimus ką nors padaryti“.

q1) Vežimas turi eiti į dešinę: jei mato 0, pakeičia jį į 1 ir lieka q1 būsenoje, jei mato 1, keičia jį į 0 ir lieka q1 būsenoje, jei mato _, tai grįžta atgal 1 langeliu „nori kažko kito“, t.y. pereina į būseną q2. Savo samprotavimus surašykime į atlikėjo lentelę. Norėdami sužinoti sintaksę, žr. programos žinyną)

q2) Dabar apibūdinkime „vežimo troškimą“ q2. Turime grįžti į pradinę padėtį. Norėdami tai padaryti: jei matome 1, paliekame jį ir liekame būsenoje q2 (su tuo pačiu noru pasiekti simbolių serijos pabaigą); jei matome 0, paliekame jį ir toliau judame į kairę būsenoje q2; matome _ – per 1 langelį pasislenka į dešinę. Dabar esate ten, kur to reikalaujama užduoties sąlygomis. einame į būseną q0.

Programą, kaip veikia, galite pamatyti vaizdo įraše:

2 uždavinys. Duota: baigtinė 0 ir 1 seka (001101011101). Būtina juos išrašyti po šios sekos per tuščią langelį ir šioje sekoje pakeisti 0. Pavyzdžiui:

Iš 001101011101 gauname 000000000000 1111111.

Kaip matote, po šios sekos buvo parašyti septyni vienetai, o jų vietose yra nuliai.

Pradėkime diskusiją. Nustatykime, kurių būsenų ir kiek reikia vežimui.

q1) pjūklas 1 - pataisykite jį iki nulio ir pereikite į kitą būseną q2 (įvedama nauja būsena, kad vežimėlis vienu važiavimu nepakeistų visų vienetų į nulius)

q2) nieko nekeiskite, pereikite prie sekos pabaigos

q3) kai tik vežimėlis pamato tuščią langelį, jis žengia žingsnį į dešinę ir nubrėžia 1, jei mato 1, jis juda toliau ir pasirašo pabaigoje esantį simbolį. Kai tik nubrėžiu vienetą, pereiname prie būsenos q4

q4) einame per užrašytus vienetus nieko nekeisdami. Kai tik pasiekiame tuščią langelį, skiriantį seką nuo vienetų, pereiname į naują būseną q5

q5) šioje būsenoje nieko nekeisdami einame į sekos pradžią. Pasiekiame tuščią langelį, apsisukame ir pereiname į būseną q1

Vežimas įgaus būseną q0, kai būsenoje q1 pereis iki šios sekos pabaigos ir susidurs su tuščiu langeliu.

Gauname tokią programą:

Toliau pateiktame vaizdo įraše galite pamatyti, kaip veikia Turingo mašina.

Kas, pasiskolinęs idėją iš Emil Pašto, sugalvojo, manoma, 1936 m. Nepaisant gana sudėtingo formalaus apibrėžimo, idėja iš esmės paprasta. Norėdami tai suprasti, pasivaikščiokime po Vikipedijos puslapius.

Pirmiausia patenkame į puslapį, kuris iš tikrųjų vadinasi: „Turingo mašina“.

Turingo mašina

Tiuringo mašina (MT)- matematinė abstrakcija, vaizduojanti bendrą skaičiavimo mašiną. 2010 metais Alanas Turingas pasiūlė formalizuoti algoritmo sąvoką.

Tiuringo mašina yra baigtinių būsenų mašinos modelio išplėtimas ir, remiantis Church-Turingo teze, gali imituoti (davus atitinkamą programą) bet kurią mašiną, kurios veiksmas yra pereiti iš vienos diskrečios būsenos į kitą.

Tiuringo mašina apima begalybę abiem kryptimis juostele, padalintas į ląsteles ir valdymo įtaisas su baigtiniu skaičiumi būsenų.

Valdymo įtaisas gali judėti į kairę ir dešinę išilgai juostos, skaityti ir įrašyti kai kurių baigtinių abėcėlės simbolius į langelius. Išsiskiria ypatingai tuščia simbolis, užpildantis visus juostos langelius, išskyrus tuos iš jų (galutinį skaičių), ant kurių užrašyti įvesties duomenys.

Valdymo įtaise yra perėjimo lentelė, kuris reiškia algoritmą, realizuojamas duota Tiuringo mašina. Kiekviena lentelės taisyklė nurodo mašinai, atsižvelgiant į esamą būseną ir esamame langelyje stebimą simbolį, įrašyti naują simbolį į šį langelį, pereiti į naują būseną ir perkelti vieną langelį į kairę arba dešinę. Kai kurios Tiuringo mašinos būsenos gali būti pažymėtos kaip terminalas, o eiti į bet kurį iš jų reiškia darbo pabaigą, algoritmo stabdymą.

Tiuringo mašina vadinama deterministinis, jei kiekvienas būsenos ir juostelės simbolio derinys lentelėje atitinka daugiausia vieną taisyklę ir nedeterministinis kitaip.

Taigi, Tiuringo mašina yra matematinė abstrakcija, spekuliatyvi žmogaus proto konstrukcija: gamtoje ji neegzistuoja. Arba yra? Iš karto ateina į galvą, kaip veikia gyva ląstelė. Bent du pavyzdžiai.

1. Gaminti baltymus ląstelėje, naudojant kompleksinį fermentą – RNR polimerazę – informacija nuskaitoma iš DNR, savotiškos Turingo mašinos informacinės juostos. Tačiau čia pačios juostos ląstelės neperrašomos, bet šiaip procesas labai panašus: RNR polimerazė sėdi ant DNR ir juda išilgai jos viena kryptimi, o tuo tarpu sintetina RNR grandinę – į DNR panašią nukleorūgštį. Paruošta RNR, atsijungusi nuo fermento, perneša informaciją į ląstelių organelius, kuriuose gaminami baltymai.

2. DNR klaidų taisymo procesas dar labiau panašus į Tiuringo mašiną – jos taisymas. Čia DNR polimerazė kartu su kitais baltymais juda išilgai DNR juostos ir nuskaito abi jos puses (genominė DNR, kaip žinoma, yra dvi susipynusios grandinės, kuriose yra ta pati informacija). Jei puselių informacija nesutampa, DNR polimerazė paima vieną iš jų kaip mėginį, o kitą „pataiso“.

Ši analogija nėra nauja, o Vikipedijoje ji taip pat aprašyta straipsnyje „Molekulinis kompiuteris“:

molekulinis kompiuteris

Biomolekulinis skaičiavimas arba molekuliniai kompiuteriai ar net DNR – arba RNR – skaičiavimas – visi šie terminai atsirado tokių įvairių mokslų, kaip molekulinė genetika ir kompiuterinės technologijos, sankirtoje.

Biomolekulinis skaičiavimas yra bendras įvairių metodų, vienaip ar kitaip susijusių su DNR arba RNR, pavadinimas. DNR skaičiavime duomenys pateikiami ne nulių ir vienetų pavidalu, o molekulinės struktūros, sukurtos DNR spiralės pagrindu, forma. Duomenų skaitymo, kopijavimo ir tvarkymo programinės įrangos vaidmenį atlieka specialūs fermentai.

Visos biologinės informacijos saugojimo sistemos, taigi ir DNR kompiuterių, pagrindas yra vandenilio atomų, įtrauktų į azoto junginius (adeniną, timiną, citoziną ir guaniną), gebėjimas tam tikromis sąlygomis traukti vienas kitą, sudarydami nevalentinį ryšį. porų. Kita vertus, šios medžiagos gali susijungti su cukraus molekulės (dezoksiribozės) ir fosfato deriniais, sudarydamos vadinamuosius nukleotidus. Nukleotidai savo ruožtu lengvai sudaro dešimčių milijonų bazių ilgio polimerus. Šiose supermolekulėse fosfatas ir dezoksiribozė atlieka atraminės struktūros vaidmenį (jie keičiasi grandinėje), o azoto junginiai koduoja informaciją.

Pasirodo, molekulė yra kryptinga: ji prasideda fosfato grupe ir baigiasi dezoksiriboze. Ilgos DNR grandinės vadinamos grandinėmis, trumpos – oligonukleotidais. Kiekviena DNR molekulė atitinka kitą DNR – vadinamąjį Watson-Crick komplementą. Ji turi priešingą kryptį nei pradinė molekulė. Dėl adenino pritraukimo prie timino ir citozino prie guanino susidaro garsioji dviguba spiralė, leidžianti DNR padvigubėti ląstelių dauginimosi metu. Dvigubos problema sprendžiama naudojant specialų fermentinį baltymą – polimerazę. Sintezė prasideda tik tada, kai jos komplemento gabalėlis yra prijungtas prie DNR.Ši savybė aktyviai naudojama molekulinėje biologijoje ir molekulinėje kompiuterijoje. Iš esmės DNR+polimerazė yra Turingo mašinos įgyvendinimas, susidedantis iš dviejų juostų ir programuojamo valdymo pulto. Konsolė nuskaito duomenis iš vienos juostos, apdoroja juos pagal kažkokį algoritmą ir įrašo į kitą juostą. Polimerazė taip pat nuosekliai nuskaito pradinius duomenis iš vienos juostos (DNR) ir jos pagrindu suformuoja juostą tarsi su skaičiavimų rezultatais (Watson-Crick priedas).

Šiek tiek fantastiškos perspektyvos tik kursto mūsų smalsumą. Tuo tarpu mes dar ne viską išsiaiškinome apie Turingo mašiną. Kaip prisimenate, Vikipedijos straipsnyje tai buvo vadinama baigtinės būsenos mašinos plėtiniu. Kas yra baigtinių būsenų mašina? Laimei, yra nuoroda į ją. Perėję tai sužinome, kad:

Valstybės mašina

Abstraktūs automatai sudaro pagrindinę diskrečiųjų modelių klasę, tiek kaip savarankiškas modelis, tiek kaip pagrindinis Tiuringo mašinų, atminties automatų, baigtinių būsenų mašinų ir kitų informacijos transformatorių komponentas.

Su kiekvienu apibrėžimu mes vis labiau įsiskverbiame į grynosios matematikos sritį. Kalba tampa griežtesnė, atsiranda formalūs apibrėžimai, susidedantys iš matematinių simbolių. Jei judėsime toliau, prieisime prie algoritmų teorijos ir apskaičiuojamumo teorijos. Galite ilgai keliauti po Vikipedijos puslapius, tačiau geriau apsirūpinkite vandeniu ir maistu, jei nuklysite į aksiomų ir apibrėžimų dykumą arba bent jau patikimas nuorodas į matematikos vadovėlius, pavyzdžiui http:/ /www.mccme.ru/free-books/ arba straipsniai iš žurnalo „Potencialus“ ;)

Tikiuosi, kad šis paaiškinimas jums padės šiek tiek aiškiau suprasti, kas tiksliai yra Turingo mašina?

Grįžkime prie šio termino istorijos.

Taigi, kaip jau minėjome, Alanas Turingas pasauliui papasakojo apie savo mašiną 1937 metais vadinamojoje Church-Turing tezėje. Straipsnyje „Alanas Turingas“ bus pasakojama apie Alaną Turingą, pirmąjį kompiuterių mokslo pradininką ir įsilaužėlį, kaip parašyta atminimo lentoje viešbutyje, kuriame jis gimė. Čia nepateiksime viso straipsnio teksto, tačiau jis pats nėra labai išsamus.

Alanas Turingas

Turingas, Alanas Mathesonas(1912 m. birželio 23 d. – 1954 m. birželio 7 d.) – anglų matematikas, logikas, kriptografas, Tiuringo mašinos išradėjas.

Pačiame straipsnyje daugiau apie Turingo kūrybą: be teksto apie Tiuringo mašiną, kurį pateiksime vėliau, teigiama, kad jis dirbo ties „užšalimo problema“ (Juokinga, ar ne? Kompiuterių dar nebuvo). , taip pat nebuvo „Windows“ sistemos, bet jau buvo užšalimo problema.); herojiška istorija apie tai, kaip Turingas per Antrąjį pasaulinį karą nulaužė Enigmos kodą ir taip išgelbėjo Didžiąją Britaniją; faktas, kad jis yra dirbtinio intelekto teorijos įkūrėjas, taip pat garsiojo Turingo testo paminėjimas. Šiais laikais šis testas nebėra taip dažnai naudojamas kaip mokslinės fantastikos istorijos prielaida, tačiau žmogaus mašinoje problema visada išliks klasika, kaip Izaoko Asimovo ir Stanislovo Lemo romanai.

Nepaisant savo senamadiško pobūdžio, Turingo testas netikėtai atsirado šiuolaikiniame interneto komunikacijos pasaulyje. Pavyzdžiui, galite susidurti su dviejų ICQ vartotojų dialogo tekstu, iš kurių vienas yra „botas“, o užduotis yra nustatyti, kuris iš jų. Arba nepažįstamas vartotojas, galbūt ICQ robotas, gali pasibelsti į jūsų duris. Ar atpažįsti jį? Studijuodami teoriją galite laiku pritaikyti Tiuringo testą ir nebūti apgauti. Galite pradėti studiją nuo atitinkamo Vikipedijos straipsnio, tada sekite nuorodas, pateiktas straipsnio pabaigoje:

Turingo testas

Turingo testas- 1950 m. Alano Turingo straipsnyje „Skaičiavimo mašinos ir intelektas“ pasiūlytas testas, skirtas patikrinti, ar kompiuteris yra protingas žmogiškąja šio žodžio prasme.

Teisėjas (žmogus) natūralia kalba susirašinėja su dviem pašnekovais, kurių vienas yra žmogus, kitas – kompiuteris. Jei teisėjas negali patikimai nustatyti, kas yra kas, kompiuteris išlaikė testą. Daroma prielaida, kad kiekvienas iš pašnekovų siekia būti pripažintas asmenybe. Kad testas būtų paprastas ir universalus, susirašinėjimas sumažinamas iki tekstinių pranešimų.

Susirašinėjimas turėtų vykti kontroliuojamais intervalais, kad teisėjas negalėtų daryti išvadų pagal atsakymų greitį. (Turingo laikais kompiuteriai reagavo lėčiau nei žmonės. Dabar ši taisyklė būtina, nes jie reaguoja daug greičiau nei žmonės.)

Testą įkvėpė saloninis žaidimas, kuriame svečiai, rašydami klausimus ir skaitydami atsakymus, bandė atspėti kitame kambaryje esančio žmogaus lytį. Originalioje Turingo formuluotėje asmuo turėjo apsimesti priešingos lyties asmeniu, o testas truko 5 minutes. Šios taisyklės šiuo metu nėra būtinos ir nėra bandymo specifikacijos dalis.

Turingas pasiūlė testą, kuris, jo nuomone, pakeistų beprasmį klausimą „ar mašina gali mąstyti? į konkretesnį.

Turingas numatė, kad kompiuteriai galiausiai išlaikys jo testą. Jis tikėjo, kad iki 2000 m. kompiuteris su 1 milijardu bitų atminties (apie 119 MB) galės apgauti teisėjus 30 % laiko per 5 minučių testą. Ši prognozė nepasitvirtino. (Tiesa, pirmajame Loebnerio konkurse IBM PC 386 kompiuterinė programa „PC Therapist“ sugebėjo suklaidinti 5 iš 10 teisėjų, tačiau jos rezultatas nebuvo įskaitytas, o 1994 m. konkursas buvo apsunkintas.) Turing taip pat prognozavo, kad kombinacija „mąstymo mašina“ nebus laikoma oksimoronu, o kompiuterių mokymas atliks svarbų vaidmenį kuriant galingus kompiuterius (tam pritaria dauguma šiuolaikinių tyrinėtojų).

Iki šiol nė viena programa nepriartėjo prie testo išlaikymo. Tokios programos kaip ELIZA kartais privertė žmones patikėti, kad jie kalbasi su žmogumi, kaip neoficialiame eksperimente, vadinamame AOLiza. Tačiau tokios „sėkmės“ nereiškia, kad reikia išlaikyti Tiuringo testą. Pirma, tokiuose pokalbiuose dalyvaujantis asmuo neturėjo pagrindo manyti, kad kalbasi su programa, o tikro Turingo testo metu asmuo aktyviai bando nustatyti, su kuo jis kalba. Antra, dokumentuoti atvejai dažniausiai būna pokalbių kambariuose, tokiuose kaip IRC, kur daugelis pokalbių yra fragmentiški ir beprasmiai. Trečia, daugelis IRC vartotojų anglų kalbą vartoja kaip antrąją ar trečiąją kalbą, o beprasmiškas programos atsakas greičiausiai priskiriamas kalbos barjerui. Ketvirta, daugelis vartotojų nieko nežino apie Eliza ir panašias programas ir negali atpažinti visiškai nežmoniškų klaidų, kurias daro šios programos.

Kasmet vyksta kalbančių laidų konkursas, o labiausiai žmogiškai, teisėjų nuomone, įteikiamas Loebnerio prizas. Už programą skiriamas papildomas prizas, kuris, teisėjų nuomone, išlaikys Turingo testą. Ši premija dar neįteikta.

A.L.I.C.E programa parodė geriausią rezultatą Turingo teste. testą laimėjęs 3 kartus (2000, 2001 ir 2004 m.).

Nuorodos

Turingas A. M. Skaičiavimo mašinos ir intelektas. // In: Hofstader D., Dennett D. The Eye of the Mind. - Samara: Bakhrakh-M, 2003. - 47-59 p.
Knyga anglų kalba: Rogeris Penrose'as „The Emperor’s New Mind“.
Alano Turingo straipsnis:
- Alanas Turingas, „Skaičiavimo mašinos ir intelektas“, Mind, t. LIX, Nr. 236, 1950 spalis, p. 433-460.
- Prisijungęs:
G. Oppy ir D. Dowe straipsnis apie Turingo testą iš Stanfordo filosofijos enciklopedijos (anglų k.)
„Turingo testas: po 50 metų“ apžvelgia 50 metų darbą su Tiuringo testu iš 2000 metų perspektyvos.

Vėl grįžkime prie Tiuringo mašinos. Straipsnio apie Alaną Turingą ištraukoje teigiama, kad Tiuringo mašinos koncepcija pirmą kartą buvo pasiūlyta kaip dalis vadinamųjų. Church-Turingo tezė:

Ištrauka iš Vikipedijos straipsnio „Alanas Turingas“

Bet kuri intuityviai apskaičiuojama funkcija yra iš dalies apskaičiuojama arba, lygiavertiškai, apskaičiuojama tam tikra Tiuringo mašina.

Alanas Turingas pasiūlė (žinoma kaip Church-Turing tezė), kad bet koks algoritmas intuityvia šio žodžio prasme gali būti pavaizduotas lygiaverte Tiuringo mašina. Apskaičiuojamumo sampratos išaiškinimas remiantis Tiuringo mašinos koncepcija (ir kitomis lygiavertėmis sąvokomis) atvėrė galimybę griežtai įrodyti įvairių masės problemų (tai yra problemų, kaip rasti vieningą tam tikros klasės problemų sprendimo metodą) algoritminį neišsprendžiamumą. problemų, kurių sąlygos tam tikrose ribose gali skirtis). Paprasčiausias algoritmiškai neišsprendžiamos masės problemos pavyzdys yra vadinamoji algoritmo pritaikomumo problema (taip pat vadinama stabdymo problema). Jį sudaro: reikia rasti bendrą metodą, kuris leistų savavališkai Tiuringo mašinai (nurodytai jos programa) ir savavališkai pradinei šios mašinos juostos būsenai nustatyti, ar mašinos veikimas bus baigtas per ribotą skaičių žingsnių arba tęsis neribotą laiką.

Straipsnyje „The Church-Turing Thesis“ jie apie jį rašo taip:

Church-Turingo disertacija

Church-Turingo disertacija– pagrindinis teiginys daugeliui mokslo sričių, tokių kaip skaičiavimo teorija, kompiuterių mokslas, teorinė kibernetika ir kt. Šį teiginį XX amžiaus trečiojo dešimtmečio viduryje padarė Alonzo Church ir Alanas Turingas.

Paprasčiausia forma ji teigia, kad bet kuri intuityviai apskaičiuojama funkcija yra iš dalies apskaičiuojama arba lygiavertiškai apskaičiuojama tam tikra Tiuringo mašina.

Church-Turingo tezės negalima griežtai įrodyti ar paneigti, nes ji nustato „lygybę“ tarp griežtai formalizuotos iš dalies apskaičiuojamos funkcijos sąvokos ir neformalios „intuityviai apskaičiuojamos funkcijos“ sąvokos.

Church-Turing fizikos disertacija skaito: Bet kurią funkciją, kurią gali apskaičiuoti fizinis įrenginys, gali apskaičiuoti Tiuringo mašina.

Iš šios kryžkelės galima pereiti prie, pavyzdžiui, apskaičiuojamumo teorijos. Arba galite pabandyti išsiaiškinti, kas yra ši paslaptinga bažnyčia, su kuria Alanas Turingas pateikė savo disertaciją.

Universali Tiuringo mašina

Universali Tiuringo mašina vadinama Tiuringo mašina, kuri gali pakeisti bet kurią Tiuringo mašiną. Gavusi programą ir įvesties duomenis kaip įvestis, apskaičiuoja atsakymą, kurį iš įvesties duomenų būtų apskaičiavusi Tiuringo mašina, kurios programa buvo pateikta kaip įvestis.

Formalus apibrėžimas

Bet kurios deterministinės Tiuringo mašinos programą galima parašyti naudojant kokią nors baigtinę abėcėlę, susidedančią iš būsenų simbolių, skliaustų, rodyklių ir pan.; pažymėkime šią mašinos abėcėlę kaip Σ 1 (\displaystyle \Sigma _(1)). Tada universali Tiuringo mašina U abėcėlės klasės automobiliams Σ 2 (\displaystyle \Sigma _(2)) Ir kįvesties juostos vadinamos Tiuringo mašina su k+1įėjimo juosta ir abėcėlė Σ 1 ∪ Σ 2 (\displaystyle \Sigma _(1) \cup \Sigma _(2)) kad jei kreipsitės dėl pirmojo kįrašo įvesties reikšmę ir toliau k+1 yra teisingai parašytas kokios nors Tiuringo mašinos kodas U atsakymas bus toks pat, kaip ir naudojant šiuos įvesties duomenis M 1 (\displaystyle M_(1)), arba dirbs neribotą laiką, jei M 1 (\displaystyle M_(1)) nesiliaus su šiais duomenimis.

Universalioji Tiuringo mašinos teorema teigia, kad tokia mašina egzistuoja ir modeliuoja kitas mašinas su daugiausia kvadratiniu sulėtėjimu (ty jei originali mašina pagamino tžingsnių, tada universalusis nebegamins ct 2). Šios teoremos įrodymas yra konstruktyvus (sukurti tokią mašiną nėra sunku, tereikia atidžiai aprašyti). Teoremą pasiūlė ir įrodė Turingas 1936–1937 m.

Programinės įrangos diegimas Delphi programavimo kalba yra gana paprastas. Vieną iš šių įgyvendinimų galima rasti svetainėje http://kleron.ucoz.ru/load/24-1-0-52. Galima atsisiųsti ir įrašyti į Excel failą.

Nedeterministinė Tiuringo mašina

Tikimybinė Tiuringo mašina

Deterministinės Tiuringo mašinos apibendrinimas, kai iš bet kokios juostos būsenos ir reikšmių mašina gali atlikti vieną iš kelių (galime suskaičiuoti, neprarandant bendrumo, du) galimų perėjimų, o pasirinkimas daromas tikimybiškai. (metant monetą).

Tikimybinė Tiuringo mašina yra panaši į nedeterministinę Tiuringo mašiną, tačiau vietoj nedeterministinio perėjimo mašina pasirenka vieną iš variantų su tam tikra tikimybe.

Taip pat yra alternatyvus apibrėžimas:

Tikimybinė Tiuringo mašina yra deterministinė Tiuringo mašina, kuri papildomai turi aparatinį atsitiktinių bitų šaltinį, kurių bet kokį skaičių, pavyzdžiui, ji gali „sutvarkyti“ ir „įkelti“ į atskirą juostą, o tada naudoti skaičiavimuose įprastu būdu. MT.

Klasė algoritmų, kurie tikimybinėje Tiuringo mašinoje užbaigia daugianario laiką ir pateikia atsakymą su mažesne nei 1/3 paklaida, vadinama BPP klase.

Apsvarstykite Tiuringo mašinos veikimą.

Tiuringo mašina yra begalinė juosta, padalinta į ląsteles ir vežimėlį (skaitymo ir spausdinimo įrenginį), kuris juda juosta.

Taigi Tiuringo mašina formaliai apibūdinama dviejų abėcėlių rinkiniu:

A=(a1, a2, a3, …, an) – išorinė abėcėlė, naudojama šaltinio duomenims įrašyti

Q=(q1, q2, q3,…, qm) - vidinė abėcėlė, apibūdina skaitymo-spausdinimo įrenginio būsenų rinkinį.

Kiekviename juostos langelyje gali būti simbolis iš išorinės abėcėlės A = (a0,a1,…,an) (mūsų atveju A=(0, 1))

Leidžiami Tiuringo mašinos veiksmai:

1) įrašyti bet kurį išorinės abėcėlės simbolį į juostos langelį (simbolis, kuris buvo anksčiau, yra perrašytas)

2) pereiti į gretimą langelį

3) pakeiskite būseną į vieną iš tų, kurias rodo vidinis abėcėlės simbolis Q

Tiuringo mašina yra automatas, valdomas stalu.

Aukščiau pateiktoje lentelėje abėcėlė A =(0, 1, _) (yra 3 simboliai) ir vidinė abėcėlė Q=(q1, q2, q3, q4, q0), q0 yra būsena, dėl kurios vežimas sustoja.

Panagrinėkime keletą problemų sprendimo būdų. Turingo mašiną galite atsisiųsti svetainės skiltyje ATSISIŲSTI.

Dabar apibrėžkime vežimo būsenas. Aš juos vadinu „vežti troškimus ką nors padaryti“.

q1) Vežimas turi eiti į dešinę: jei mato 0, pakeičia jį į 1 ir lieka q1 būsenoje, jei mato 1, keičia jį į 0 ir lieka q1 būsenoje, jei mato _, tai grįžta į 1 langelį „nori kažko kito“, t.y. pereina į būseną q2. Savo samprotavimus surašykime į atlikėjo lentelę. Norėdami sužinoti sintaksę, žr. programos žinyną)

Programą, kaip veikia, galite pamatyti vaizdo įraše:

2 uždavinys. Duota: baigtinė 0 ir 1 seka (001101011101). Būtina juos išrašyti po šios sekos per tuščią langelį ir šioje sekoje pakeisti 0. Pavyzdžiui:

Iš 001101011101 gauname 000000000000 1111111.

Kaip matote, po šios sekos buvo parašyti septyni vienetai, o jų vietose yra nuliai.

Pradėkime diskusiją. Nustatykime, kurių būsenų ir kiek reikia vežimui.

q1) pjūklas 1 - pataisykite jį iki nulio ir pereikite į kitą būseną q2 (įvedama nauja būsena, kad vežimėlis vienu važiavimu nepakeistų visų vienetų į nulius)

q2) nieko nekeiskite, pereikite prie sekos pabaigos

q4) einame per užrašytus vienetus nieko nekeisdami. Kai tik pasiekiame tuščią langelį, skiriantį seką nuo vienetų, pereiname į naują būseną q5

q5) šioje būsenoje nieko nekeisdami einame į sekos pradžią. Pasiekiame tuščią langelį, apsisukame ir pereiname į būseną q1

Vežimas įgaus būseną q0, kai būsenoje q1 pereis iki šios sekos pabaigos ir susidurs su tuščiu langeliu.

Gauname tokią programą:

Toliau pateiktame vaizdo įraše galite pamatyti, kaip veikia Turingo mašina.

Tiuringo mašina (MT)- abstrakčiųjų atlikėjų (abstrakčių skaičiavimo mašinų). Buvo pasiūlyta Alanas Turingas V 1936 mįforminti sąvoką algoritmas.

Turingo mašina yra plėtinys baigtinių būsenų mašina ir, pasak Church-Turingo disertacija, gali imituoti visus kitus vykdytojus (nurodant pereinamojo laikotarpio taisykles), kurie kažkaip įgyvendina žingsnis po žingsnio skaičiavimo procesą, kuriame kiekvienas skaičiavimo žingsnis yra gana elementarus.

Turingo mašinos dizainas

Tiuringo mašina yra begalinė abiem kryptimis. juostele(Galimos Tiuringo mašinos, turinčios keletą begalinių juostų), suskirstytos į ląsteles ir valdymo įtaisas, galintis būti viename iš būsenų rinkinys. Galimų valdymo įrenginio būsenų skaičius yra baigtinis ir tiksliai nurodytas.

Valdymo įtaisas gali judėti į kairę ir į dešinę išilgai juostos, skaityti ir įrašyti tam tikros baigtinės abėcėlės simbolius į juostos langelius. Išsiskiria ypatingai tuščia simbolis, užpildantis visus juostos langelius, išskyrus tuos iš jų (galutinį skaičių), ant kurių užrašyti įvesties duomenys.

Valdymo įtaisas veikia pagal perėjimo taisyklės, kurie atspindi algoritmą, realizuojamasši Tiuringo mašina. Kiekviena perėjimo taisyklė nurodo mašinai, atsižvelgiant į esamą būseną ir dabartiniame langelyje stebimą simbolį, įrašyti naują simbolį į šį langelį, pereiti į naują būseną ir perkelti vieną langelį į kairę arba dešinę. Kai kurios Tiuringo mašinos būsenos gali būti pažymėtos kaip terminalas, o eiti į bet kurį iš jų reiškia darbo pabaigą, algoritmo stabdymą.

Tiuringo mašina vadinama deterministinis, jei kiekvienas būsenos ir juostelės simbolio derinys lentelėje atitinka daugiausia vieną taisyklę. Jei yra pora „juostos simbolis – būsena“, kuriai yra 2 ar daugiau nurodymų, tokia Tiuringo mašina vadinama nedeterministinis .

Turingo mašinos aprašymas

Konkreti Tiuringo mašina apibrėžiama išvardijant abėcėlės A raidžių rinkinio elementus, būsenų rinkinį Q ir taisyklių rinkinį, pagal kurį mašina veikia. Jie turi formą: q i a j →q i1 a j1 d k (jei galva yra būsenoje q i, o raidė a j parašyta stebimoje ląstelėje, tai galva pereina į būseną q i1, langelyje rašoma a j1 vietoj j galva daro judesį d k, kuris turi tris parinktis: viena ląstelė į kairę (L), viena ląstelė į dešinę (R), likti vietoje (N)). Kiekvienai įmanomai konfigūracijai yra tiksliai viena taisyklė. Nėra taisyklių tik galutinei būsenai, kai automobilis sustoja. Be to, turite nurodyti galutinę ir pradinę būsenas, pradinę konfigūraciją juostoje ir mašinos galvutės vietą.

Tiuringo mašinos pavyzdys

Pateiksime MT pavyzdį, skirtą skaičių dauginimui unarinė skaičių sistema. Mašina veikia pagal šias taisykles:

Taisyklės	Taisyklės


q 0 × → q 1 × R



	q 6 × → q 7 × R
q 2 × → q 3 × L
q 3 1 → q 4 aR


q 4 × → q 4 × R

Padauginkime MT 3 iš 2 vienetų sistemoje:

Protokolas nurodo pradinę ir galutinę MT būseną, pradinę konfigūraciją juostoje ir mašinos galvutės vietą (pabrauktas simbolis).

Turingo užbaigtumas

Pagrindinis straipsnis: Turingo užbaigtumas

Galima sakyti, kad Tiuringo mašina yra paprasčiausia skaičiavimo mašina su tiesine atmintimi, kuri pagal formalias taisykles transformuoja įvesties duomenis naudodama seką. elementarūs veiksmai.

Veiksmų elementarumas slypi tame, kad veiksmas pakeičia tik mažą duomenų dalį atmintyje (Turingo mašinos atveju tik vieną langelį), o galimų veiksmų skaičius yra baigtinis. Nepaisant Turingo mašinos paprastumo, ji gali apskaičiuoti viską, ką galima apskaičiuoti bet kurioje kitoje mašinoje, kuri atlieka skaičiavimus naudodama elementarių veiksmų seką. Ši savybė vadinama užbaigtumas.

Vienas iš natūralių būdų įrodyti, kad skaičiavimo algoritmai, kuriuos galima įgyvendinti vienoje mašinoje, gali būti įgyvendinami kitoje, yra pirmosios mašinos modeliavimas antroje.

Imitacija yra tokia. Pirmosios mašinos programos (darbo taisyklių) aprašymas pateikiamas į antrojo įrenginio įvestį. D ir įvesties duomenis X, kuris turėjo patekti į pirmosios mašinos įvestį. Būtina aprašyti tokią programą (antrojo įrenginio veikimo taisykles), kad atlikus skaičiavimus išvestis būtų tokia pati, kokią grąžintų pirmoji mašina, jei gautų duomenis kaip įvestį X.

Kaip buvo sakyta, Tiuringo mašinoje galima imituoti (nurodant perėjimo taisykles) visus kitus vykdytojus, kurie kažkaip įgyvendina žingsninio skaičiavimo procesą, kuriame kiekvienas skaičiavimo žingsnis yra gana elementarus.

Turingo mašinoje galite imituoti Pašto automobilis, įprasti Markovo algoritmai ir bet kokia paprastiems kompiuteriams skirta programa, kuri įvesties duomenis paverčia išvesties duomenimis naudodama tam tikrą algoritmą. Savo ruožtu Tiuringo mašina gali būti imituojama naudojant įvairius abstrakčius vykdytojus. Kviečiami atlikėjai, kuriems tai įmanoma Turingas baigtas(Turingas baigtas).

Yra paprastiems kompiuteriams skirtų programų, kurios imituoja Turingo mašinos veikimą. Tačiau reikia pažymėti, kad šis modeliavimas yra neišsamus, nes Tiuringo mašinoje yra abstrakti begalinė juosta. Begalinės juostos su duomenimis neįmanoma visiškai imituoti kompiuteryje su ribota atmintimi (bendra kompiuterio atmintis - RAM, standieji diskai, įvairios išorinės laikmenos, registrai ir procesoriaus talpykla ir kt. - gali būti labai didelė, bet vis dėlto visada baigtinė ).

Tiuringo mašinos variantai

Tiuringo mašinos modelį galima išplėsti. Galima apsvarstyti Turingo mašinas su savavališku juostų skaičiumi ir daugiamates juostas su įvairiais apribojimais. Tačiau visos šios mašinos yra sukomplektuotos ir yra sumodeliuotos naudojant įprastą Tiuringo mašiną.

Tiuringo mašina, veikianti pusiau begalinėje juostoje

Kaip tokios informacijos pavyzdį apsvarstykite šią teoremą: Bet kuriai Tiuringo mašinai yra lygiavertė Tiuringo mašina, veikianti pusiau begalinėje juostoje.

Panagrinėkime Yu. G. Karpovo pateiktą įrodymą knygoje „Automatų teorija“. Šios teoremos įrodymas yra konstruktyvus, tai yra, pateiksime algoritmą, pagal kurį bet kuriai Tiuringo mašinai galima sukurti ekvivalentinę Tiuringo mašiną su deklaruojama savybe. Pirmiausia atsitiktinai sunumeruojame MT darbo juostos langelius, tai yra, nustatome naują informacijos vietą juostoje:

Tada pernumeruojame langelius ir manysime, kad simbolio „*“ nėra MT žodyne:

Galiausiai pakeisime Tiuringo mašiną padvigubindami jos būsenų skaičių ir pakeiskime skaitymo-rašymo galvutės poslinkį taip, kad vienoje būsenų grupėje mašinos veikimas būtų lygiavertis jos veikimui šešėlinėje zonoje, o kitoje būsenų grupėje, kad mašina veiktų taip, kaip originali mašina veikia neužtemdytoje srityje. Jei MT operacijos metu aptinkamas simbolis „*“, tai reiškia, kad skaitymo ir rašymo galvutė pasiekė zonos ribą:

Pradinė naujosios Tiuringo mašinos būsena nustatoma vienoje ar kitoje zonoje, priklausomai nuo to, kur originalioje juostoje buvo skaitymo-rašymo galvutė pradinėje konfigūracijoje. Akivaizdu, kad kairėje nuo ribojančių žymenų „*“ juosta nenaudojama lygiavertėje Tiuringo mašinoje.

Nusprendžiau paaiškinti žmonijai algoritminių skaičiavimų principą. Faktas yra tas, kad J. Turingas buvo kompiuterių amžiaus pranašas, todėl jis tiesiog negalėjo nepasakyti žmonėms, kas yra algoritmas. Taigi jis sugalvojo abstrakčią mašiną, kuri buvo pavadinta jo vardu. Tai yra, pavardė. Bet paimkime eilės tvarka...

Esmė paprastais žodžiais

Reikėtų nedelsiant atkreipti dėmesį į svarbų dalyką: Tiuringo mašina yra išskirtinai spekuliacinis įrenginys. Gamtoje nieko panašaus nėra. Tačiau yra kompiuterių modelių. Net ir aktyvių. Tačiau jie yra ne kas kita, kaip modeliai.

Kodėl taip? Nes diskusijos objektas – nesibaigianti juosta, kurios pilnas fizinis egzistavimas šiame mokslo ir technikos vystymosi etape įmanomas tik teoriškai.

Juosta susideda iš ląstelių, kaip grandžių grandinė. Ląstelėse yra duomenų, pavyzdžiui, abėcėlės simbolių. Na, arba nuliai ir vienetai. Apskritai viskas, kas tinka automatiniam apdorojimui. Tai atlieka judanti mašinos dalis.

Kaip tai veikia

Judanti dalis yra skaitytojas ir rašytojas. Kažkokia gudrybė, galinti perskaityti ląstelių turinį, įrašyti į jas kažką savo ir, svarbiausia, veikti pagal gautus rezultatus.

Be to, mašina vienu metu gali perkelti tik vieną langelį. Dešinėn, kairėn, kur reikia atlikti skaičiavimus. Čia tu kažką pridėjai – reikia pajudėti, kad ką nors atimtum. Ir tada vėl sulenkite. Ir taip tol, kol bus atlikta užduotis. Juosta yra begalė, yra pakankamai galimybių bet kokiai operacijai.

Tiesą sakant, Alanas Turingas kaip tik bandė pabrėžti, kad kiekvienas skaičiavimas, kad ir koks sudėtingas būtų, gali būti atliekamas etapais, žingsnis po žingsnio, suskaidant problemą į elementarias sudedamąsias dalis. Tai yra algoritmo esmė.

Įvairūs variantai

Naujokai kibernetikai pažvelgė į Tiuringo mašiną ir suprato, kad nėra kuo skųstis. Iš tiesų, kompiuterinės programos turėtų būti kuriamos remiantis algoritmais – žingsnis po žingsnio instrukcijų vykdymas.

Tuo pačiu metu Alano Turingo šlovė persekiojo daugelį, o pasekėjai pradėjo, kaip sakoma, gaudyti jos žvilgsnius. Jie pradėjo kurti daugiamates Tiuringo mašinas su daugybe juostų, „pusiau begalinių“ ir kt.

Pasistengsime įnešti bent šiek tiek aiškumo į šį chaosą ir apsvarstysime realias aptariamo įrenginio galimybes.

Nedeterministinis- tai Tiuringo mašina, kuri veikia aukščiau aprašytoje juostoje su ląstelėmis pagal situaciją, kuri susidaro tam tikrame skaičiavimo etape. Kur jai reikia eiti, ten ji ir eis, kitaip tariant.
Deterministinis– su konkrečiomis instrukcijomis. Pavyzdžiui, jei ląstelėje, kurioje yra vykdomoji mašina, parašyta raidė A, tada nori nenori reikia pereiti prie gretimos su raide B.
Pilnas- galintis apskaičiuoti viską, ką galima apskaičiuoti atliekant žingsnis po žingsnio operacijas. Jis netgi gali imituoti mašiną mašinoje, emuliatorių, kuris su algoritmais aprašo kito panašaus įrenginio veikimą.
Universalus- gali padaryti viską, ką gali bet kuris Turingo mašinos variantas. Apskritai, bet koks, net dar neišrastas. Žinoma, ji yra pilna.

Praktinė nauda

Žinoma, algoritmas yra sudėtingesnė sąvoka nei tiesiog žingsnis po žingsnio judėjimas vienmatėje erdvėje. Juk galima išsišakoti, kilpinti, grįžti atgal ir naudoti paprogrames.

Be to, praktiškai neįmanoma imituoti begalinio skaičiaus langelių, kuriuose yra duomenų, jau vien todėl, kad kompiuterinės įrangos galimybės yra ribotos.

Tačiau yra programų, kurios imituoja Tiuringo mašinas, skirtas mokiniams mokyti. Pradedantieji programuotojai skatinami kurti įvairius algoritmus, pavyzdžiui, ieškoti, keisti, pridėti, pertvarkyti raides ląstelėse.

Vadinasi, Tiuringo mašinos privalumai yra būtent tokie, kokius numatė jos kūrėjas, kompiuterių amžiaus pranašas: aiškiai parodoma algoritminių skaičiavimų esmė.

Ankstesnės publikacijos:

Paskutinį kartą redaguota: 2013-04-01 10:58:05

Medžiagos etiketės: ,