Masini Turing - Notiuni de Baza

Publicat: 03 Ian 2012 00:00

Notiuni de baza pentru masini Turing



Privite ca limbaj de progr. masinile T. au o singura struct. de baze si pot primi la intrare doar siruri de simboluri iar operatiile executate sunt de miscare stanga sau dreapta a unui cursor in circuitul de intrare impreuna cu scanarea simbolului din pozitia curenta a cursorului si posibilitatea de a scrie in pozitia curenta.


Ramificarile operatiilor sunt facute conform cu starea in care se afla masina si cu simbolul curent scanat.Este o masina f. simpla, primitiva, care desi prezinta slabiciuni evidente, are o mare putere de calcul si este f. utila in analiza algoritmilor. Se va descrie modelul masinii turing deterministe, adica care are un singura stare initiala. Conceptul de masina T. corespunde masinii cu mai multe benzi care consta din:

1. o multime finita de stari ca in cazul automatului finit; stari de control ale masinii
2. din una sau mai multe benzi de lucru semiinfinite care sunt impartite in celule si fiecare banda este echipata cu un cap de citire-scriere care se poate misca spre stanga/dreapta scanand (citind) celulele benzii, in modul o celula la un moment dat (capul este echivalent cursorului). Nr. de benzi este fixat pt. masina.
3. o extrabanda cu capul de citire-scriere coresp. numita banda de intrare.

Termenul de banda semiinfinita inseamna ca exista o prima celula (cea mai din stanga) si nu exista cea mai din dreapta celula.De asemenea, cand capul de citire-scriere scaneaza cea mai din stanga celula, nu se mai poate misca spre stanga.in orice mom. disp. se afla intr-una din starile lui permise.Disp. poate citi continutul unei celule scanate, poate schimba cont. celulei scanate pe o banda de lucru prin scrierea unui nou simbol, poate muta capul de citire/scriere spre stanga/dr. si isi poate schimba starea interna. Toate aceste op. formeaza un pas si sunt definite in mod unic de o fct de tranzitie care depinde de starea curenta interna si de simbolul citit de pe banda.

Nu se permite sa se schimbe cont. benzii de intrare. O masina T. M incepe prelucrarea unui cuvant de intrare W aflat pe banda de intrare, W pe care il contine prin scanarea primei celule.Cuvantul w e urmat de de un simbol numit spatiu (blank).La inceput fiecare celula de pe benzile de lucru contin blank.

Trebuie sa citesti

Cum este cariera de traducator - iata cum se desfasoara lucrurile la INOVA
Cum este cariera de traducator - iata cum se desfasoara lucrurile la INOVA

Odata cu evolutia globalizarii si a schimburilor comerciale intre tari, a relocalizarii companiilor, a dezvoltarii multinationalelor, Romania a devenit o piata de desfacere a produselor europene si noneuropene, o zona atractiva pentru investitorii straini care au gasit aici forta de munca mai

Sfaturi pentru a juca la SuperEnalotto
Sfaturi pentru a juca la SuperEnalotto

Cu siguranță știți câte numere SuperEnalotto trebuie să alegeți pentru a câștiga. Știți, de asemenea, unde și când au loc extragerile SuperEnalotto și care sunt șansele de a câștiga la această loterie. Cu

Top 15 deserturi populare in intreaga lume
Top 15 deserturi populare in intreaga lume

Deserturile difera de la o tara la alta: unele sunt usoare si fructate, iar altele vin cu cele mai neasteptate combinatii de gustrui. Ti-am pregatit aici o lista cu cele mai populare deserturi din intreaga lume: Franta: Crème Brûlée Crème brûlée este un desert

Ce trebuie sa stii pentru un hairstyling perfect: tipuri de par si metode de ingrijire
Ce trebuie sa stii pentru un hairstyling perfect: tipuri de par si metode de ingrijire

Pentru multe femei, parul reprezinta cel mai bun atu. Drept si fin, voluminos si cret, usor de aranjat sau dificil de controlat, parul fiecarei femei este frumos in felul sau. Modul in care iti aranjezi parul tine de preferinte, dar probabil ca deja ai aflat ca exista anumite limitari cand vine

5 sfaturi pentru a te prezenta exemplar la un interviu de angajare
5 sfaturi pentru a te prezenta exemplar la un interviu de angajare

Poate cel mai greu au resimtit perioada de pandemie studentii, odata cu mutarea cursurilor online. Astfel, o mare parte dintre cei 400.000 de studenti, atat cat exista in Romania potrivit Institutului National de Statistica, au plecat acasa, au parasit centrele universitare si s-au adaptat din mers

Teste Online

Test - ATMOSFERA

TEST DE EVALUARE SECVENŢIALĂ\r\nATMOSFERA

mai multe »
Acest site foloseste Cookie-uri.
Folosim cookie-uri pentru a personaliza continutul si reclamele, pentru a oferi caracteristici specifice retelelor sociale si pentru a analiza traficul nostru. De asemenea, impartasim informatii despre felul in care ne utilizati site-ul, cu partenerii nostri de pe retelele sociale, de publicitate si de statistica in conformitate cu Politica de confidentialitate. Va puteti administra preferintele in Setari cookie.