Masini Turing - Notiuni de Baza

label Referate autorenew 2025-09-29, 17:00 history_edu Burdescu Dumitru
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.