Otvori glavni izbornik

Promjene

Obrisano 35 bajtova ,  prije 12 godina
čišenje (AWB)
:Poput Turingovih strojeva, [[P′′]] koristi beskonačnu traku simbola (bez slučajnog pristupa) i poprilično minimalistički skup instrukcija. Ali ove su instrukcije vrlo različite, te stoga, za razliku od Turingovih strojeva, P′′ me treba održavati različito stanje, jer svu funkcionalnost "sličnu memoriji" može pružiti samo traka. Umjesto prepisivanja trenutnog simbola, može obaviti inkrementiranje [[modularna aritmetika|modularnom aritmetikom]] nad njim. P′′ također posjeduje par instrukcija za ciklus, ispitujući simbol praznine. Unatoč svojoj minimalističkoj prirodi, postao je roditeljski formalni jezik ostvarenog i (za zabavu) korištenog programskog jezika zvanog [[Brainfuck]].
 
Kao dodatak općenitim računskim modelima, neki jednostavniji računski modeli su korisni za posebne, ograničene primjene. [[Regularni izraz]]i, na primjer, se koriste za specificiranje uzoraka stringa u mnogim kontekstima, od programske podrške za uredsku produktivnost pa do [[programski jezik|programskih jezika]]. Drugi formalizam matematički istovjetan regularnim izrazima, [[konačni automat|konačni automati]]i, se koristi u dizajnu elektroničkih krugova i pri rješavanju nekih problema. [[Kontekstno neovisna gramatika|Kontekstno neovisne gramatike]] se rabe prilikom specifikacije sintakse programskih jezika. Nedeterministički [[potisni automat|potisni automati]]i su drugi formalizam istovjetan kontekstno neovisnim gramatikama. [[Primitivno rekurzivna funkcija|Primitivno rekurzivne funkcije]] su potklasa rekurzivnih funkcija.
 
Različiti modeli računanja imaju sposobnost obavljanja različitih zadataka. Jedan način mjerenja moći računskog modela jest proučavanje klase [[formalni jezik|formalnih jezika]] koje model može generirati - ovo vodi ka[[Chomskyjeva hijerarhija|Chomskyjevoj hijerarhiji]] jezika.
 
*[http://www.cs.uky.edu/~lewis/texts/theory/title.pdf] Dobar udžbenik u PDF formatu Forbesa D. Lewisa, koji pokriva teme formalnih jezika, automata i gramatika. Naglasak je više na predstavljanju pregleda rezultata i njihovim primjenama, radije nego na pružanju dokaza.
[[Kategorija: Teorija računanja| ]]
 
[[Kategorija: Teorija računanja| ]]
 
[[ar:نظرية التحسيب]]
[[en:Theory of computation]]
[[es:Teoría de la computación]]
[[ko:계산 이론]]
[[ja:計算理論]]
[[ko:계산 이론]]
[[pl:Teoria obliczeń]]
[[pt:Teoria da computação]]
3.196

uređivanja