Rezumat: Dedicat simple, modele de calcul clasice (descriere) algoritm (algoritmiziruemogo proces) - masina A.Tyuringa, opri problema unei astfel de mașini (de încetare a acestui proces) și leagă această problemă la problema algoritmică clasică a egalității de cuvinte în semigrupuri libere.
De ce avem nevoie de modele computationale simple?
Până acum, a fost convenabil să ne referim la experiența de programare. vorbind despre algoritmi, programe, interpreți, execuție pas-cu-pas etc. Acest lucru ne-a permis să ignorăm detaliile construirii acestor sau alți algoritmi sub pretextul că cititorul le poate readuce cu ușurință (sau cel puțin nu fiecare cititor din viața lui a fost spus de un interpret de pascal pe pascal).
Dar, în unele cazuri, acest lucru nu este suficient. Să presupunem, de exemplu, vrem să dovedească imprecizie algoritmică unor probleme în a determina care nu spune nimic despre programele (în această secțiune, de exemplu, dovedim imprecizie a problemei cuvânt în semigrupuri. Definit de generatoare și relații). Acest lucru se face de obicei. Arătăm că problema opririi se reduce la această problemă. Pentru a face acest lucru, simulează funcționarea unui algoritm arbitrar în ceea ce privește problema în cauză (ce înseamnă acest lucru din exemplul de mai jos). Este important pentru noi ca definiția algoritmului să fie cât mai simplă posibil.
Astfel, planul nostru este după cum urmează. Vom descrie destul de simplu definit clase de mașini (care pot fi alese în moduri diferite, vom utiliza așa-numita masina Turing), și apoi să declare că orice funcție calculabil poate fi calculată pe o astfel de mașină, și apoi arată că problema oprirea unei mașini Turing poate fi redusă la problema egalității cuvintelor într-o grupare semigrup.
Mașini Turing: definiție
Mașina Turing are o bandă nesfârșită în ambele direcții. împărțit în pătrate (celule). În fiecare celulă, un anumit simbol poate fi scris dintr-un set fix (pentru o anumită mașină) finită. numit alfabetul acestei mașini. Unul dintre simbolurile alfabetului este selectat și se numește "spațiu". Se presupune că inițial întreaga bandă este goală, adică este umplută cu spații.
Mașina Turing poate schimba conținutul benzii cu un cap special de citire și scriere. care se mișcă de-a lungul benzii. În fiecare moment capul se află într-una din celule. Mașina Turing pe capul de ce un personaj ce vede, și, în funcție de acest lucru (și starea sa internă) decide ce să facă, care este un simbol al înregistrării în celula curentă și în cazul în care să se deplaseze după aceea (la stânga, la dreapta sau la stânga la fața locului). De asemenea, se schimbă starea internă a mașinii (presupunem că aparatul nu este de numărare banda are o memorie finită. Este un număr finit de stări interne). Încă trebuie să fim de acord asupra locului unde începem și când terminăm munca.
Astfel, pentru a specifica o mașină Turing, trebuie să specificați următoarele obiecte:
- un set finit arbitrar A (alfabet); elementele sale se numesc simboluri;
- un caracter selectat (spațiu sau caracter liber);
- un set finit S. numit set de state;
- o anumită stare, numită starea inițială;
- tabel de conversie. care determină comportamentul mașinii în funcție de stare și de simbolul curent (a se vedea mai jos);
- un anumit subset, ale cărui elemente sunt numite stări finale (o dată în această stare, mașina se oprește).
Masa de tranziție este aranjată după cum urmează: pentru fiecare pereche este indicată tripla. Aici, schimbarea este una dintre numerele -1 (spre stânga), 0 (în loc) și 1 (spre dreapta). Astfel, masa de tranziție este o funcție de tipul S x A -> S x A x. Se determină pe acele perechi în care statul nu este final.
Rămâne să descriem comportamentul mașinii Turing. În fiecare moment există o configurație. pliere a conținutului bandă (tehnic vorbind, conținutul benzii este arbitrară hartă Z -> A), poziția curentă capului (un număr întreg) și starea curentă a aparatului (elementul S). Conversia la următoarea configurație are loc în regulile naturale: ne uităm la masa, ce să facă pentru stat și pentru simbolul, adică, aflăm o nouă stare a mașinii, schimbați simbolul unui specificat și apoi mutați capul spre stânga, dreapta sau la stânga în loc. În acest caz, dacă noua condiție este una dintre cele finale, operația mașinii se termină. Rămâne de acord asupra modului în care trimitem informații la intrarea mașinii și la ceea ce este considerat rezultatul muncii sale. Vom presupune că alfabetul mașinii, pe lângă spațiu, conține simbolurile 0 și 1 (și, eventual, alte câteva simboluri). Intrarea și ieșirea mașinii vor fi secvențe finite de zerouri și una (cuvinte binare). Cuvântul de intrare este înregistrat pe o bandă goală, capul mașinii este plasat în prima sa colivie, mașina este adusă la starea inițială și pornește. Dacă mașina se oprește, rezultatul este un cuvânt binar. care poate fi citit, pornind de la poziția capului și se deplasează spre dreapta (până când caracterul apare diferit de 0 și 1).
Astfel, orice mașină Turing definește o anumită funcție parțială în cuvintele binare. Toate aceste funcții se pot numi în mod natural calculat pe mașinile Turing.
Mașini Turing: discuții
Desigur, definiția noastră conține multe detalii specifice care ar putea fi schimbate. De exemplu, o bandă poate fi infinită doar într-o singură direcție. Puteți da mașinii două benzi. Putem presupune că mașina poate scrie fie un nou simbol, fie o mișcare, dar nu ambele. Puteți să limitați alfabetul. luând în considerare, să spunem, că ar trebui să existe exact 10 simboluri în ea. Puteți cere că la sfârșit nu există nimic pe bandă, cu excepția rezultatului lucrării (restul celulelor ar trebui să fie goale). Toate aceste și multe alte modificări nu schimbă clasa funcțiilor computerizate pe mașinile Turing. Desigur, există unele schimbări inofensive. De exemplu, dacă interziceți mutarea aparatului la stânga, atunci acest lucru schimbă radical cazul, de fapt, banda va deveni inutilă, deoarece va fi imposibil să reveniți la vechile înregistrări.
Cum să înțelegeți ce schimbări sunt inofensive și care nu sunt? Se pare că este necesară o experiență practică de programare pe mașinile Turing, cel puțin puțin. După aceea, puteți să vă imaginați deja posibilitățile mașinii fără a scrie complet programele și să fiți ghidat doar printr-o descriere aproximativă. De exemplu, să descriem o mașină care dublează cuvântul de intrare (face cuvântul XX dacă intrarea era X).
Dacă aparatul vede un spațiu (cuvântul de intrare este gol), acesta încheie lucrarea. Dacă nu, își amintește caracterul actual și îl marchează (în alfabet, în plus față de caracterele 0 și 1 vor fi și "variantele lor" și "). Apoi se mută în dreapta celulei goale, apoi scrie acolo o copie a simbolului memorat. Apoi se mișcă la stânga până la marcaj; îngropându-se în etichetă, trecând înapoi și amintit următorul personaj și așa mai departe, până când a copiat întregul cuvânt.
Având o experiență. puteți vedea pentru toate aceste fraze anumite fragmente ale programului pentru mașina Turing. De exemplu, cuvântul „amintesc caracterul și muta la dreapta“ înseamnă că există două stări ale grupurilor, unul pentru atunci când memorata zero și unu când unitatea stocată. iar în cadrul fiecărui grup mișcarea spre dreapta este programată la prima celulă goală.
Având o experiență mai mică, puteți înțelege că în această descriere există o eroare în care nu există un mecanism de oprire atunci când întregul cuvânt este copiat, deoarece copii ale caracterelor nu se deosebesc de caracterele cuvântului original. De asemenea, este clar modul de corectare a unei greșeli, trebuie să scrieți caractere speciale ca copii și, în ultima etapă, să eliminați toate semnele.
77. Arătați că funcția "inversare", transformând cuvântul înapoi, poate fi calculată pe o mașină Turing.
Un alt exemplu de raționament informal: să explicăm de ce nu puteți folosi caractere suplimentare, cu excepția 0. 1 și a unui caracter gol. Să fie o mașină cu un alfabet mare de simboluri N. Vom construi o mașină nouă care va simula lucrarea celui vechi, dar fiecare bloc din celula veche va avea un bloc de celule noi noi. Dimensiunea blocului (numărul k) va fi fixată astfel încât în interiorul blocului să fie posibilă codarea tuturor simbolurilor alfabetului mare cu zerouri și altele. Caracterele inițiale sunt 0. 1 și goale va fi codificat ca 0. urmat de caractere (k-1) goale, 1. urmate de caractere (k-1) goale și un grup de simboluri k goale. În primul rând, trebuie să extindeți literele cuvântului introdus cu o distanță k. ceea ce se poate face fără simboluri suplimentare (ajungeți la litera extremă, împingeți-o înapoi, apoi ajungeți la următoarea, împingând-o și cea extremă și așa mai departe); este necesar doar să înțelegem că este posibil să se identifice sfârșitul unui cuvânt ca poziție urmată de mai mult de simbolurile goale k. În mod evident, în acest proces, trebuie să stocăm în memorie o cantitate finită de informații, astfel încât acest lucru este posibil. După aceasta, este deja posibil să simuleze operațiunile mașinii sursă în pași, iar pentru aceasta și memoria finită (într-un număr finit de state) este suficientă, deoarece doar un mic cartier al capului mașinii simulate este important pentru noi. În cele din urmă, trebuie să comprimăm rezultatul înapoi.
Afirmația că fiecare funcție calculată este calculată pe o mașină Turing este numită teza Turing. Desigur, înțelesul său depinde de ce se înțelege prin cuvintele "funcția calculată". Dacă le înțelegem în sens vag, intuitiv ( „funcție este calculată algoritmic, care este clar, fără echivoc, reguli clare“, sau ceva de genul asta), desigur, cu privire la orice dovadă a tezei Turing poate fi vorba. Putem spune doar că practica veche de secole a omenirii de la Euclid la Knut nu sa întâlnit cu un exemplu de algoritm care nu poate fi scris ca un program al unei mașini Turing, etc. Cu toate acestea, un alt argument (nu prea convingător) este dat mai jos.
În încheierea discuției, să menționăm argumentul de mai sus în favoarea faptului că orice funcție computată este calculată pe o mașină Turing. Să fie o funcție. pe care o persoană le poate calcula. În același timp, el, firește, ar trebui să folosească un creion și o hârtie, ca și cantitatea de informații. pe care o poate păstra "în minte", este limitată. Vom presupune că scrie pe foi de hârtie separate. În plus față de foaia actuală, există un teanc de hârtii în dreapta și o grămadă de stânga; în oricare dintre ele puteți pune foaia curentă. terminând cu lucrul acesta, și dintr-o altă grămadă pentru a lua următoarele. O persoană are un creion și o radieră. Deoarece litere foarte mici, care nu poate fi văzut, numărul de foi de state disting clar desigur, și putem presupune că, la fiecare punct de pe foaia este înregistrată o singură literă dintr-un finit (deși foarte mare) a alfabetului. Omul are și memorie finită. astfel încât starea sa este un element al unui set finit. În acest caz, puteți face unele de masă, care este scris, ce rezultatul muncii sale pe o foaie cu conținutul început în această stare (adică pe foaia, în ce stare se va o persoană și foaia următoare va fi luată dintr-un pachet). Acum este clar că acțiunea umană este doar a se potrivi cu masina Turing, cu o mare (dar finit) alfabet și o mare (dar finit) numărul de stări interne.
Articole similare
Trimiteți-le prietenilor: