Trang 286
Lý thuyết Ôtômát & NNHT - Khoa Công NghThông Tin
Chương 9 Máy Turing
PDA vmt mt nào đómnh hơn rt nhiu FSA.
NNPNC-PDA vn còn gii hn. Bên ngoài nó gì?
FSA và PDA khác nhau bn cht ca b lưu trtm thi.
Nếu PDA dùng hai, ba stack, mt hàng (queue), hay mt thiết
b lưu trkhác nào đó thì sc mnh sthếnào?
Mi thiết b lưu tr định nghĩa mt loi ôtômát mi và thông
qua nó mt hngôn ngmi?
Ôtômát có th được mrng đến chng nào? Kh năng mnh
nht có thca ôtômát? Nhng gii hn ca vic tính toán?
Máy Turing ra đời và khái nim vstính toán có tính máy
móc hay gii thut (mechanical or algorithmic computation).
Máy Turing là khá thô sơ, nhưng đủ sc để bao trùm các quá
trình rt phc tp và lun đề Turing (Turing thesis) cho rng
bt kquá trình tính toán nào thc hin được bng các máy tính
ngày nay, đều có ththc hin được bng máy Turing.
Trang 287
Lý thuyết Ôtômát & NNHT - Khoa Công NghThông Tin
Chương 9 Máy Turing
9.1 Máy Turing chun
9.2 Kết hp các máy Turing cho các công vic phc tp
9.3 Lun đề Turing
Trang 288
Lý thuyết Ôtômát & NNHT - Khoa Công NghThông Tin
Máy Turing chun
Định nghĩa 9.1
Mt máy Turing M được định nghĩa bng bby
M= (Q, Σ, Γ, δ, q0, , F),
Q là tp hu hn các trng thái ni,
Σ tp hu hn các kí hiu được gi là bng chcái ngõ nhp,
Γ tp hu hn các kí hiu được gi là bng chcái băng,
δ hàm chuyn trng thái,
∈Γ mt kí hiu đặc bit,
gi là khong trng (blank),
q0Q trng thái khi đầu,
FQ tp các trng thái kết thúc.
Control unit
Input, Storage,
Output
Trang 289
Lý thuyết Ôtômát & NNHT - Khoa Công NghThông Tin
Máy Turing chun (tt)
Trong định nghĩa chúng ta githiết rng Σ⊆Γ-{}.
Hàm δ được định nghĩa như sau
δ: Q×Γ→Q×Γ×{L, R}
được din dch như sau: Các đối sca δ trng thái hin
hành ca ôtômát và hiu băng đang được đọc. Kết qu mt
trng thái mi ca automat, mt kí hiu băng mi thay thếcho
hiu đang được đọc trên băng và mt sdi chuyn đầu đọc
sang phi hoc sang trái.
dδ(q0, a) = {q1, d, R}
abc dbc
Trng thái niq0Trng thái niq1
Trang 290
Lý thuyết Ôtômát & NNHT - Khoa Công NghThông Tin
d
Xét mt máy Turing được định nghĩa như sau
Q= {q0, q1}, Σ= {a, b}, Γ= {a, b, }, F= , còn δ được định
nghĩa
δ(q0, a) = (q1, a, R)δ(q1, a) = (q0, a, L)
δ(q0, b) = (q1, b, R)δ(q1, b) = (q0, b, L)
δ(q0, ) = (q1, , R)δ(q1, ) = (q0, , L)
Xét hot động ca M trong trường hp sau
Trường hp này máy không dng li và rơi vào mt vòng lp
vô tn(infinite loop)
ab ab
q0q1
ab
q0