Inačica od 28. ožujka 2015. u 18:45 uredi Peregrin Falcon (razgovor \| doprinosi) Automatski ophođeni suradnici 1.256 edits Nema sažetka uređivanja ← Starija izmjena		Inačica od 2. veljače 2020. u 13:28 uredi ukloni ovu izmjenu MaGaBot (razgovor \| doprinosi) Automatski ophođeni suradnici, Botovi 57.780 edits m lektura (budući da -> jer) Novija izmjena →
Redak 6: # Rekurzivno prebrojiv formalni jezik je [[rekurzivno prebrojiv skup\|rekurzivno prebrojiv]] podskup [[skup]]a svih mogućih riječi nad [[abeceda(računarstvo)\|abecedom]] [[formalni jezik\|jezika]]. # Rekurzivno prebrojiv jezik je formalni jezik za koji postoji [[Turingov stroj]] (ili neka druga izračunljiva funkcija) koji može prebrojiti sve valjane nizove znakova jezika. Uočimo da, ako je jezik beskonačan, dani algoritam prebrojavanja može biti odabran tako da izbjegava ponavljanja, ~~budući da~~jer možemo provjeriti je li niz znakova proizveden za broj ''n'' "već prije" proizveden za broj manji od ''n''. Ako je već prije proizveden, koristimo izlaz za ulaz za broj ''n+1'' mjesto njega (rekurzivno), ali opet, provjeravamo je li "novi". # Rekurzivno prebrojiv jezik jest formalni jezik za kojeg postoji Turingov stroj (ili neka druga izračunljiva funkcija) koji će stati i prihvatiti ako primi bilo koji niz znakova koji je element jezika kao ulaz, a inače može stati i ne prihvatiti niz ili se vrtjeti u beskonačnoj petlji u slučaju ulaza niza znakova koji nije u jeziku. Kontrastirajmo ovo sa [[rekurzivni jezik\|rekurzivnim jezicima]], koji zahtijevaju da Turingov stroj stane u svim slučajevima.

Rekurzivno prebrojiv jezik: razlika između inačica