Máy Turing
(Turing Machine)
Nội dung:
•
Mô hình TM
•
TM nhận dạng ngôn ngữ
•
TM tính toán hàm số nguyên
•
Các kỹ thuật xây dựng TM
Chương 7:
1

Mô hình TM
Định nghĩa: TM là một hệ thống gồm 7 thành phần
M (Q, Σ, Γ, δ, q
0
, B, F)
●
Q : tập hữu hạn các trạng thái
●
Σ : bộ ký hiệu nhập
●
Γ : tập hữu hạn các ký hiệu được viết trên băng
●
δ : hàm chuyển Q x Γ → Q x Γ x {L, R, Ø}
●
q
0

Giả sử : δ(q, X
i
) = (p, Y, L)
•
Nếu i - 1 = n thì X
i
là B
•
Nếu i = 1 thì không có ID kế tiếp (đầu đọc không được phép
vượt qua cận trái của băng.
•
Nếu i > 1 ta viết:
X
1
X
2
...X
i-1
qX
i
...X
n
⊢

X
1
X
2
...X
i-2

i+1
...X
n
Và với : δ(q, X
i
) = (p, Y, Ø)
X
1
X
2
...X
i-1
qX
i
...X
n
⊢

X
1
X
2
...X
i-2
X
i-1
pYX
i+1
...X
n

1 ⊢ XX q
2
YY ⊢ X q
2
XYY ⊢ XX q
0
YY ⊢
XXYq
3
Y ⊢ XXYYq
3
⊢ XXYYq
4
Ví dụ: thiết kế TM chấp nhận L = {0
n
1
n
| n > 0}
Đặt TM M(Q, Σ, Γ, δ, q
0
, B, F) với
Q = {q
0
, q
1
, q
2
, q
3
, q