"ucqav" - 1 õppematerjal

Rekursiooni ja keerukusteooria eksami konspekt

..,an} on lindi tähestik, a0 on tühik, millega on täidetud lindi kõik positsioonid, mis ei sisalda „kasulikku informatsiooni”, Q on olekute tähestik, 
 δ : Q×Σ → P(Q×Σ×{L,R,S}) on üleminekufunktsioon; Q0 ⊆ Q on lähteolekute hulk; F ⊆ Q on lõppolekute hulk. DEF: Turingi masina töötakt on binaarne relatsioon ⊢ konfiguratsioonide hulgal, nii et 
 uqav ⊢ urbv, kui (r,b,S) ∈ δ(q,a); uqav ⊢ ubrv, kui (r,b,R) ∈ δ(q,a); ucqav ⊢ urcbv, kui (r,b,L) ∈ δ(q,a). M(x) = y - masin jõub sisendi x korral mingi arvu taktide pärast lõppkonfiguratsiooni qfy (olek+sõne)
 M(x) → qf - masin jõub sisendi x korral mingi arvu taktide pärast lõppolekusse qf M(x) < ∞ - masin jõub sisendi x korral mingi arvu taktide pärast lõppolekusse M(x) = ∞ - masin ei peatu x korral kunagi või peatub jõudmata lõppkonfiguratsiooni Aktsepteeriv Turingi masin on selline, millel on aktsepteeriv lõppolek qa ja tagasilükkav qr