y Turing Chương 44 MMááy Turing Chương
y Turing nh nghĩĩa ma mááy Turing Ngôn ngữữ ththừừa nha nhậận đưn đượợc vc vàà ngôn ng ngôn ngữữ xxáác đc địịnh đư nh đượợcc
nh toáánn Lý thuyếết tt tíính to Lý thuy Lý thuyết tính toán (Theory of Computation) (Theory of Computation) (Theory of Computation)
MMááy Turing y Turing ĐĐịịnh ngh Ngôn ng CCáác hc hààm tm tíính đư CCáác ngôn ng LuLuậận đn đềề Turing
PGS.TS. Phan Huy Kháánhnh PGS.TS. Phan Huy Kh khanhph@vnn.vn khanhph@vnn.vn
KKỹỹ thuthuậật xây d
y Turing nh đượợc bc bởởi mi mááy Turing t kê đệệ quyquy quy vàà liliệệt kê đ
c ngôn ngữữ đ đệệ quy v Turing--Church Church y Turing t xây dựựng mng mááy Turing
nh giớới ni nộộii
Chương 44 Chương 4 Chương y Turing MMááy Turing Máy Turing
y Turing MMởở rrộộng cng cáác mc mááy Turing MMááy turing không đơn đ MMááy Turing v Ôtômat tuy Văn ph y turing không đơn địịnhnh y Turing vạạn năng n năng Ôtômat tuyếến tn tíính gi Văn phạạm cm cảảm ngm ngữữ ccảảnhnh
2/2/5858
MMởở đ đầầuu
Mô tMô tảả mmááy Turing đơn đ
y Turing đơn địịnhnh
n NN ng không thểể đo đoáán nhn nhậận NN
Ôhh đ
MMááy Turing đơn đ
y Turing đơn địịnh (Deterministic Turing Machine) g
nh (Deterministic Turing Machine) gồồm :m :
MMộột băng v
Ôhh đẩẩy xuy xuốống không th aannbbnnccnn ddùù ccóó hai bhai bộộ nhnhớớ llớớn tn tùùy ýy ý ĐĐểể ththừừa nha nhậận an annbbnnccnn, ph, phảải ti tììm kim kiếếmm
MMộột đt đầầu đu đọọcc--ghi (Read/Write Head) di chuy
MMộột tt tậập hp hợợp hp hữữu hu hạạn cn cáác trc trạạng th
p ôtômat kháác,c, đ đóó llàà ccáác mc mááy Turing y Turing y Turing c nhau căn bảản gin giữữa ma mááy Turing
MMộột trt trạạng th
ng tháái đi đầầuu
MMộột tt tậập hp hợợp cp cáác trc trạạng th
ng tháái thi thừừa nha nhậận (cu
n (cuốối)i)
MMộột ht hààm chuy
o/ra (IO Tape) : t băng vàào/ra (IO Tape) : n trên băng ghi (Read/Write Head) di chuyểển trên băng ng tháái trong đ i trong đóó ccóó ::
ccáác lc lớớp ôtômat kh SSựự khkháác nhau căn b vvàà ô đ ô đẩẩy xuy xuốống :ng : y Turing chỉỉ ccóó mmộột bt bộộ nhnhớớ llớớn tn tùùy ý y ý MMááy Turing ch MMááy Turing c y Turing cóó ththểể đ đọọc vc vàà ghighi CCáách sch sửử ddụụng bng bộộ nhnhớớ llàà tutuỳỳ ý,ý,
m chuyểển tin tiếếpp
Y
X
a
b
a
b
b
# #
. . .
Alan Turung Alan Turung 1954) : (19121954) : (1912 nhnhàà ToToáán hn họọc c ngưngườời Anh, i Anh, ngưngườời đi đầầu tiên u tiên nghiên cứứuu nghiên c t ôtômat lý thuyếết ôtômat lý thuy 1936 năm 1936 năm
qk
nguyên lý danh sááchch không hạạn chn chếế ởở nguyên lý danh s không h ng (Stack hay LIFO) đđẩẩy xuy xuốống (Stack hay LIFO)
3/3/5858
4/4/5858
Mô tMô tảả chi ti
chi tiếếtt
CCấấu hu hìình ban đ
y Turing nh ban đầầu cu củủa ma mááy Turing
Băng v
o/ra : Băng vàào/ra :
CCấấu hu hìình ban đ
nh ban đầầu cu củủa ma mááy Turing đư
y Turing đượợc mô t
như sau :: c mô tảả như sau
Câu v
LLàà mmộột bt bộộ nhnhớớ vô hvô hạạn đưn đượợc chia th MMỗỗi ô c
MMỗỗi ô còn l
Băng ch HHààm chuy
ĐĐầầu đu đọọcc--ghi n
MMááy đang
TrTrạạng th Ký tKý tựự đ đọọc đưc đượợc c ởở vvịị trtríí dư dướới đi đầầu đu đọọcc
ng thựực hic hiệện bn bằằng cng cáách đch đọọc ký hi
c ký hiệệuu
c chia thàành nhi nh nhiềều ôu ô Câu vàào w o w ** nnằằm m ởở mmúút trt tráái nhi nhấất ct củủa băng a băng i ô cóó ththểể chchứứa ma mộột ký t Tape Alphabet) t ký tựự aa nnàào đo đóó ( (Tape Alphabet) t ký hiệệu đu đặặc bic biệệt,t, i quy ướớc cc cóó ththểể kkééo do dàài vô h i vô hạạnn i ô còn lạại ci củủa băng ch c ký hiệệu tru trốống (B a băng chứứa ma mộột ký hi lank Symbol) ng (Blank Symbol) ggọọi li làà ccáác ký hi Băng chỉỉ ccóó ccậận trn tráái, ci, cậận phn phảải quy ư c tham đốối :i : m chuyểển tin tiếếp gp gồồm cm cáác tham đ ghi nằằm m ởở ô đ ô đầầu tiên c a băng (m(múút trt tráái nhi nhấất)t) ng tháái hi i hiệện hn hàành cnh củủa ma mááyy y đang ởở trtrạạng th ng tháái đi đầầu tiên, gi u tiên củủa băng u tiên, giảả ssửử q0
MMááy sy sẵẵn sn sààng th ởở vvịị trtríí đ đầầu đu đọọcc
b
a
a
b
a
b
b
# #
. . .
TrTrạạng th i tiếếp theo c Ký tKý tựự ssẽẽ ghi lên băng t ChiChiềều di chuy (qua tráái, ph (qua tr
q0
p theo củủa ma mááyy ng tháái ti ghi lên băng tạại vi vịị trtríí ký tký tựự vvừừa đa đọọc đưc đượợc c u di chuyểển cn củủa đa đầầu đu đọọcc--ghighi i, phảải hay đ ng yên) i hay đứứng yên)
5/5/5858
6/6/5858
1
y Turing HoHoạạt đt độộng cng củủa ma mááy Turing
ĐĐịịnh ngh
nh nghĩĩa ha hìình th
y Turing nh thứức mc mááy Turing
MMááy Turing đư
c mô tảả bbởởi mi mộột bt bộộ bbảảy :y :
HoHoạạt đt độộng cng củủa ma mááy Turing đư
y Turing đượợc mô t
như sau :: c mô tảả như sau
y Turing đượợc mô t , #, F) M = (Q, , , , , , q, q00, #, F) M = (Q,
trong đóó :: trong đ
MMááy đy đọọc ký hi TuTuỳỳ theo tr hhààm chuy Ghi đGhi đèè lên ký hi
lên ký hiệệu vu vừừa đa đọọc mc mộột ký hi
Di chuy
Di chuyểển đn đầầu đu đọọcc--ghi sang ph
ghi sang phảải, ho
i, hoặặc sang tr
c sang tráái mi mộột ôt ô
c ký hiệệu nu nằằm m ởở dư dướới đi đầầu đu đọọcc ng tháái hi i hiệện hn hàành,nh, theo trạạng th m chuyểển tin tiếếp cho ph ng thááii p cho phéép mp mááy thy thựực hic hiệện :n : t ký hiệệu khu kháácc
Thay đ
Thay đổổi tri trạạng th MMááy thy thừừa nha nhậận câu khi đ
ng thááii n câu khi đạạt tt tớới tri trạạng th
Q lQ làà ttậập hp hữữu hu hạạn cn cáác trc trạạng th llàà bbảảng ch llàà bbảảng ch qq00 Q lQ làà trtrạạng th F F Q lQ làà ttậập hp hợợp cp cáác trc trạạng th # # -- llàà ký tký tựự trtrốốngng
Y
X
X
Y
X
X
X
# #
. . .
ng chữữ ghi lên băng ghi lên băng ng chữữ vvààoo ng tháái đi đầầuu ng tháái thi thừừa nha nhậận,n, ng tháái thi thừừa nha nhậậnn gigiảả ssửử qj FF
: h: hààm chuy
qj
m chuyểển tin tiếếpp
7/7/5858
8/8/5858
Mô tMô tảả hhààm chuy
m chuyểển tin tiếếp p
y Turing CCấấu hu hìình cnh củủa ma mááy Turing
HHààm chuy
m chuyểển tin tiếếp :p :
CCấấu hu hìình (hay c
nh (hay cấấu hu hìình) c
y Turing nh) củủa ma mááy Turing
llàà mmộột pht phầần tn tửử ccủủa quan h
a quan hệệ : (q,
: (q, 11, , 22) ) QQ****
: Q: Q QQMM
trong đóó ::
(q, a) = (q’’, x, x, m, m), ), trong đ
ggồồm cm cáác phc phầần tn tửử (q, a) = (q
ng tháái hi
i hiệện hn hàành cnh củủa ma mááyy
Trong đóó :: Trong đ
: ph: phầần câu trên băng ph
n câu trên băng phíía trưa trướớc vc vịị trtríí đ đầầu đu đọọcc--ghighi
n câu trên băng từừ vvịị trtríí đ đầầu đu đọọcc--ghi đ
t câu ghi đếến hn hếết câu
q q QQ : tr: trạạng th 11 22
: Ph: Phầần câu trên băng t (ký tựự cucuốối ci cùùng kh (ký t
ng kháác ký t
ng #) c ký tựự trtrốống #)
CCóó ththểể viviếết gt gọọn mn mỗỗi i phphầần tn tửử ccủủa a ::
11
22
q, qq, q’’ Q ;Q ; a a ;; x x ;; M = { L, R } m m M = { L, R } L chL chỉỉ đ địịnh dnh dịịch đch đầầu đu đọọcc--ghi sang tr i (Left) ghi sang tráái (Left) R chR chỉỉ đ địịnh dnh dịịch đch đầầu đu đọọcc--ghi sang ph i (Right) ghi sang phảải (Right)
b
a
a
b
a
b
b
# #
. . .
q
hohoặặc c (q, a, x, m, q (q, a, x, m, q’’) ) hohoặặc qc qaamxqmxq’’
9/9/5858
10/10/5858
Chuyểển tin tiếếp mp mộột bưt bướớc C c C ├├ CC’’ Chuy
Chuyểển tin tiếếp mp mộột bưt bướớc C c C ├├ CC’’ Chuy
Cho c
Cho c
Cho cấấu hu hìình C = (q,
nh C = (q, 11, , 22) v) vàà CC’’ = (q= (q’’, , ’’11, , ’’22))
nh C = (q, 11, , 22) v) vàà CC’’ = (q= (q’’, , ’’11, , ’’22))
Cho cấấu hu hìình C = (q, GiGiảả ssửử 11 = = ’’11aa 22 = b= b3 3
ChuyChuyểển tin tiếếp mp mộột bưt bướớc C
a như sau :: nh nghĩĩa như sau
ChuyChuyểển tin tiếếp mp mộột bưt bướớc C
a như sau :: nh nghĩĩa như sau
11 trưtrườờng hng hợợp p 22 = = , l, lấấy y b = #b = # c C ├├ CC’’ đư đượợc đc địịnh ngh
22
’’22
11
22
’’22
11
’’11
’’22
’’11
’’11
33
33
b
a b b a b b
b
a b’ b a b b
# ...
# ...
GiGiảả ssửử 22 = b= b’’2 2 trưtrườờng hng hợợp p 22 = = , l, lấấy y b = #b = # c C ├├ CC’’ đư đượợc đc địịnh ngh TrưTrườờng hng hợợp 1 : N (q, b) = (q’’, b, b’’, R), ta c , R), ta cóó :: p 1 : Nếếu u (q, b) = (q TrưTrườờng hng hợợp 2 : N (q, b) = (q’’, b, b’’, L), ta c , L), ta cóó :: p 2 : Nếếu u (q, b) = (q (q, 11, b, b’’22) ) ├├ (q(q’’, , 11bb’’, , ’’22)) (q, vvớới i ’’11 = = 11bb’’ (q, ’’11a, a, 22) ) ├├ (q(q’’, , ’’11, ab, ab’’33)) (q, vvớới i ’’22 = ab= ab’’33
├├├
b
b a b’ a b b
# ...
b
b a b a b b
# ...
├├├
q
q’
q’
q
11/11/5858
12/12/5858
2
Chuyểển tin tiếếp nhi Chuy
p nhiềều bưu bướớcc
MMááy Turing đo
y Turing đoáán nhn nhậận câu c
n câu củủa ngôn ng
a ngôn ngữữ
Cho c
Cho cấấu hu hìình C = (q,
MMááy Turing đo
y Turing đoáán nhn nhậận câu c
n câu củủa ma mộột ngôn ng
t ngôn ngữữ như l
như làà ccáác c
ôtômat hữữu hu hạạn đã x ôtômat h
n đã xéétt
Tương t
Tương tựự trong ôhh, ta n
nh C = (q, 11, , 22) v) vàà CC’’ = (q= (q’’, , ’’11, , ’’22)) trong ôhh, ta nóói chuy
i chuyểển tin tiếếp nhi
p nhiềều bưu bướớcc
Cho w
Cho w : :
C C ├├** CC’’ nnễễuu:: k k 0 v0 vàà ccáác cc cấấu hu hìình trung gian C C C CC00 CC’’ CCkk CCii ├├ CCi+1i+1 vvớới 0
y Turing M đoáán nhn nhậận n nnễễu u :: nh trung gian C00, C, C11, . . ., C sao cho : , . . ., Ckk sao cho : , w) ├├** (q(qjj, , , , 2) v2) vớới i , , 2 2 ** y Turing thừừa nha nhậận n nnễễu u :: i 0 i i kk , w) ├├** (q(qjj, , , , 2) v2) vớới i , , 2 2 * v* vàà qqj j FF t ngôn ngữữ L đư y Turing M, L đượợc thc thừừa nha nhậận bn bởởi mi mộột mt mááy Turing M,
Câu w đượợc mc mộột mt mááy Turing M đo Câu w đư (q(q00, , , w) Câu w đượợc mc mộột mt mááy Turing th Câu w đư (q(q00, , , w) MMộột ngôn ng L = L(M), nnễễu u :: L = L(M), L(M) = { w (q(q00, , , w) L(M) = { w , w) ├├** (q(qjj, , , , 2) v2) vớới qi qj j F }F }
13/13/5858
14/14/5858
VVíí ddụụ
BiBiểểu diu diễễn đn đồồ ththịị
Cho mCho mááy Turing M
, B, F) vớới :i :
y Turing M (Q,
(Q, , , , , , q, q00, B, F) v
Q Q q0, q1, q2, q3, q4 q0, q1, q2, q3, q4 { a, b, X, Y, # }, { a, b, X, Y, # },
q0 q1 q2 q3 q4
a (q1, X, R) (q1, a, R) (q1, a, L)
b (q2, Y, L)
X (q0, X, R)
Y (q3, Y, R) (q1, Y, R) (q2, Y, L) (q3, Y, R)
# (q4, #, R)
t qua phảảii VưVượợt qua ph Vượt qua phải
đư đượợc cho b
u con a ĐĐáánh dnh dấấu con a Đánh dấu con a trtráái nhi nhấấtt trái nhất
ra rằằng hng hààm chuy
m chuyểển tin tiếếp không đư
p không đượợc đc địịnh ngh
nh nghĩĩa)a)
(d(dấấu "u "" ch" chỉỉ ra r
X/X, R X/X, R
Y/Y, R Y/Y, R
a
Y
b
X
#
Y/Y, R Y/Y, R
(q1, X, R)
(q3, Y, R)
q0
a/X, R a/X, R
b/Y, L b/Y, L
q0q0q0
q1q1q1
q2q2q2
(q1, a, R)
(q2, Y, L)
(q1, Y, R)
q1
a/a, L a/a, L
a/a, R a/a, R
(q1, a, L)
(q0, X, R)
(q2, Y, L)
q2
Y/Y, R Y/Y, R
#/#, R #/#, R
q3
(q3, Y, R)
(q4, #, R)
Y/Y, R Y/Y, R
q3q3q3
q4q4q4
q4
{ a, b } { a, b } { q4} F F { q4} c cho bởởi bi bảảng dư i đây ng dướới đây
15/15/5858
16/16/5858
MMááy Turing đo
y Turing đoáán nhn nhậận câu
n câu aa22bb22
MMááy Turing đo
y Turing đoáán nhn nhậận câu
n câu aa33bb33
CCáác chuy
c chuyểển tin tiếếp đop đoáán nhn nhậận câu aabb l
t như sau :: n câu aabb lầần lưn lượợt như sau
dãy c
dãy cáác chuy
c chuyểển tin tiếếp tp từừ câu v
câu vàào aaabbb đư
c cho như sau :: o aaabbb đượợc cho như sau
q0aabb# q0aabb# q0XaYb# q0XaYb# q0XXYY# q0XXYY# q0aaabbb# q0aaabbb# q1Xabb# q1Xabb# q1XXYb# q1XXYb# q3XXYY# q3XXYY# q1Xaabbb# q1Xaabbb# q1Xabb# q1Xabb# q1XXYb# q1XXYb# q3XXYY## q3XXYY## q1Xaabbb# q1Xaabbb# q2XXXYYY# q2XaaYbb# q2XXXYYY# q2XaaYbb# q0XXXYYY# q0XaaYbb# q0XXXYYY# q0XaaYbb# q3XXXYYY# . . . . . . . . . q3XXXYYY# . . . . . . . . . q1Xaabbb# q1Xaabbb# q2XaYb# q2XaYb# q2XaYb# q2XaYb# q2XXYY# q2XXYY# q2XXYY# q2XXYY# q4XXYY## q4XXYY## ththừừa nha nhậậnn q2XaaYbb# q2XaaYbb# q3XXXYYY# q1XXXYYb# q3XXXYYY# q1XXXYYb# q3XXXYYY# q2XXXYYY# q3XXXYYY# q2XXXYYY# q4XXXYYY## q2XXXYYY# q4XXXYYY## q2XXXYYY# q2XaaYbb# q2XaaYbb# ththừừa nha nhậận !n !
17/17/5858
18/18/5858
3
VVíí ddụụ
ĐĐịịnh ngh
nh nghĩĩaa
MMááy Turing th
y Turing thừừa nha nhậận ngôn ng
nh quy aa* + b(a+b)* n ngôn ngữữ chchíính quy aa* + b(a+b)*
c hiệện (xn (xửử lý)lý)
t câu ww llàà ththựực hi
MMááy Turing mmộột dãy c
y Turing đođoáán nhn nhậận mn mộột câu t dãy cựực đc đạại ci cáác cc cấấu hu hìình :nh :
a|a, R
(q(q00, , , w)
, w) = C= C0 0 ├├ CC11 ...
... ... ├├ CCkk = (q= (qkk, , kk, , kk) ) ├├ ...
sao cho : nghnghĩĩa la làà sao cho :
#|#, L
q0
q1
Dãy t
y
,
Ry
y a
, ,
Ly La
y a
, ,
Ry Ra
Dãy t
4q L,
y
,
Ry
a
,
Rx
b
,
Ly
3q
0q
2q
ng tháái ki kếết tht thúúcc Dãy tựự kkếết tht thúúc tc tạại mi mộột ct cấấu hu hìình cnh cóó chchứứa tra trạạng th vvàà ththừừa nha nhậậnn câucâu ww hohoặặcc nh không chứứa tra trạạng th , không còn cấấu hu hìình nnh nàào co cóó ththểể chuy ng tháái ki kếết t chuyểển đn đếến : n : Dãy tựự kkếết tht thúúc tc tạại mi mộột ct cấấu hu hìình không ch ththúúc mc màà ttừừ đ đóó, không còn c mmááy by bịị hhóócc
Rx
x
1q , hohoặặcc Dãy Dãy ccấấu u hhìình lnh làà vô hvô hạạn, mn, mááy không bao gi y không bao giờờ ddừừngng
19/19/5858
20/20/5858
TTíính xnh xáác đc địịnh đư
c (Deterministic) nh đượợc (Deterministic)
HHìình th
nh thứức hc hóóa ta tíính xnh xáác đc địịnh đư
nh đượợc c
MMộột ngôn ng
t ngôn ngữữ L đư
L đượợc xc xáác đc địịnh bnh bởởi mi mộột mt mááy Turing M
y Turing M nnễễuu ::
TTíính xnh xáác đc địịnh đư
nh đượợc cc củủa ma mááy Turing c
y Turing cóó ththểể hihiểểu như sau
u như sau : :
M thM thừừa nha nhậận Ln L
VVớới mi mọọi phi phầần tn tửử (q, a) (q, a) (q(q’’, a, a’’, m), vi (q, a)
M không c
HHààm bm bộộ phphậận Qn QG G QQGGM cM cóó ththểể ttáách th
NhNhậận xn xéét :t :
HHààm m ““ký tký tựự mmớớii””
nc :nc : QQG G GG
TTồồn tn tạại thu ngngữữ, hay ki
hay nc(q, a) = a’’ hay nc(q, a) = a
HHààm m ““di chuy
di chuyểển đn đầầu đu đọọcc”” mh :mh : QQG G MM
hay mh(q, a) =m hay mh(q, a) =m
ĐĐốối vi vớới ci cáác ôtôm ĐĐốối vi vớới mi mộột ôtôm
t quy tắắc c (q, a) QQG, tG, tồồn tn tạại nhi , m), viếết gt gọọn qama n qama’’qq’’, v, vớới m i nhiềều nhu nhấất mt mộột quy t M={L, R} i m M={L, R} M không cóó ccáác xc xửử lý vô h lý vô hạạnn ch thàành ba h nh ba hààm :m : i thuậật tot toáán cho ph n cho phéép mp mááy Turing đo t ngôn y Turing đoáán nhn nhậận mn mộột ngôn , hay kiểểm tra t nh đượợcc
HHààm m ““trtrạạng th
ng tháái mi mớớii””
ns :ns : QQG G QQ
hay ns(q, a) = q’’ hay ns(q, a) = q
m tra tíính xnh xáác đc địịnh đư c ôtômáát ht hữữu hu hạạn đơn đ t ôtômáát ht hữữu hu hạạn không đơn đ i luôn luôn tồồn tn tạại thu n đơn địịnh,nh, đi điềều đu đóó hihiểển nhiên n nhiên n không đơn địịnh,nh, i thuậật tot toáán,n,
n, không thểể chchỉỉ ra chuy ra chuyểển tin tiếếp p không phảải luôn luôn t không ph vvìì :: TTạại mi mỗỗi giai đo nnàào tio tiếếp theo s i giai đoạạn đon đoáán nhn nhậận, không th ng minh p theo sẽẽ đư đượợc chc chọọn mn mộột ct cáách tưch tườờng minh
21/21/5858
22/22/5858
MMááy Turing t
y Turing tíính hnh hààmm
Notation of Function Notation of Function
A function f(w) has:
MMááy Turing c
y Turing cóó ththểể ttíính hnh hààm theo c
m theo cáách hi
u như sau :: ch hiểểu như sau
Tham đ
Result Region: S
Domain: D
GiGiáá trtrịị trtrảả vvềề ccủủa ha hààm lm làà câu
( wf
)
Dw
( wf
)
S
MMááy Turing t
y Turing tíính mnh mộột ht hààm f : m f : nnếếu :u :
VVớới mi mộột câu v
Tham đốối ci củủa ha hààm lm làà câu v câu vàào wo w nnằằm trên băng m trên băng câu đư đượợc ghi trên băng c ghi trên băng sau khi mááy Turing k sau khi m y Turing kếết tht thúúc vic việệc xc xửử lý t w) lý ((đđọọc hc hếết w)
HHààm f đgl t
nh đượợc bc bởởi mi mộột mt mááy Turing n
y Turing nếếu tu tồồn tn tạại mi mộột t
A function may have many parameters:
m f đgl tíính đư y Turing tíính đư
mmááy Turing t
nh đượợc nc nóó
Example: Addition function
f(x, y) = x + y
y luôn luôn dừừng trong m ng trong mộột t t câu vàào wo w bbấất kt kỳỳ, m, mááy luôn luôn d ccấấu hu hìình mnh màà f(w) c trên băng f(w) cóó mmặặt t ởở trên băng
23/23/5858
24/24/5858
4
Data representation Data representation
Definition:
f
Integer Domain
M
A function is computable if there is a Turing Machine such that:
Decimal:
5
Binary:
101
Final configuration (wf
Initial configuration w
)
Unary:
11111
initial state
final state
fq
0q
We prefer unary representation:
easier to manipulate with TMs
For all
Dw Domain
25/25/5858
26/26/5858
Example Example
In other words:
is computable
,( yxf
) x
y
f
The function
M
A function is computable if there is a Turing Machine such that:
yx,
are integers
q
wf (
)
├─
wq 0
f
Turing Machine:
yx0
Input string:
unary
Initial Configuration
Final Configuration
0xy
Output string:
For all
unary
Domain
Dw
27/27/5858
28/28/5858
Input representation Input representation
Computing Function Computing Function y
x
y
x
Start
Start
1
1
1
1
0
1
0
1
1
1
1
1
initial state
0q
0q
initial state
x
y
Finish
0
1
11
1
The 0 is the delimiter that separates the two numbers
fq
final state
29/29/5858
30/30/5858
5
Computing Function Computing Function
Turing machine for function ) x
,( yxf
y
The 0 helps when we use the result for other operations
1
R,1
1
R,1
1
L,1
x
y
0
R,1
L,
1
L,0
2q
1q
0q
3q
Finish
1
11
0
1
R,
final state
fq
31/31/5858
32/32/5858
4q
Execution Example (1)
Execution Example (2)
1
1
0
1
1
Time 0
(2)
(2)
11x 11y
0q
1
R,1
1
R,1
1
L,1
x
0
R,1
L,
1
L,0
2q
1
1
0
0
Final Result x y 1 1
Time 0 y 1
1
1
1
1q
0q
3q
R,
0q
4q
33/33/5858
34/34/5858
4q
Execution Example (3)
Execution Example (4)
1
1
1
01
0
1
1
1
1
Time 1
Time 2
0q
0q
1
R,1
1
R,1
1
R,1
1
L,1
1
R,1
1
L,1
0
R,1
0
R,1
L,
L,
1
L,0
1
L,0
2q
2q
1q
1q
0q
3q
0q
3q
R,
R,
35/35/5858
36/36/5858
4q
4q
6
Execution Example (5)
Execution Example (6)
1
1
1
1
1
1
1
1
1
1
Time 3
Time 4
1q
1q
1
R,1
1
R,1
1
R,1
1
L,1
1
R,1
1
L,1
0
R,1
0
R,1
L,
L,
1
L,0
1
L,0
2q
2q
1q
1q
0q
3q
0q
3q
R,
R,
37/37/5858
38/38/5858
4q
4q
Execution Example (7)
Execution Example (8)
1
1
1
1
1
1
1
1
1
1
Time 5
Time 6
1q
2q
1
R,1
1
R,1
1
R,1
1
L,1
1
R,1
1
L,1
0
R,1
0
R,1
L,
L,
1
L,0
1
L,0
2q
2q
1q
1q
0q
3q
0q
3q
R,
R,
40/40/5858
39/39/5858
4q
4q
Execution Example (9)
Execution Example (10)
1
1
1
1
0
0
1
1
1
1
Time 7
Time 8
3q
3q
1
R,1
1
R,1
1
R,1
1
L,1
1
R,1
1
L,1
0
R,1
0
R,1
L,
L,
1
L,0
1
L,0
2q
2q
1q
1q
0q
3q
0q
3q
R,
R,
41/41/5858
42/42/5858
4q
4q
7
Execution Example (11)
Execution Example (12)
1
1
1
1
0
0
1
1
1
1
Time 9
Time 10
3q
3q
1
R,1
1
R,1
1
R,1
1
L,1
1
R,1
1
L,1
0
R,1
0
R,1
L,
L,
1
L,0
1
L,0
2q
2q
1q
1q
0q
3q
0q
3q
R,
R,
43/43/5858
44/44/5858
4q
4q
Execution Example (13)
Execution Example (14)
1
1
1
1
0
0
1
1
1
1
Time 11
Time 12
3q
4q
1
R,1
1
R,1
1
R,1
1
L,1
1
R,1
1
L,1
0
R,1
0
R,1
L,
L,
1
L,0
1
L,0
2q
2q
1q
1q
0q
3q
0q
3q
R,
R,
HALT & accept
45/45/5858
46/46/5858
4q
4q
Another Example: Another
(1)(1)
(2)(2)
Example: f(x) = 2x f(x) = 2x
Example: f(x) = 2x Another Example: f(x) = 2x Another x
is computable
)( xf
2
x
The function
1
1
1
Start
x
is integer
initial state
0q
Turing Machine:
x2
x
Input string:
unary
Finish
1
11
1
1
xx
Output string:
unary
final state
fq
47/47/5858
48/48/5858
8
TM Pseudocode for f(x) = 2x
Example TM for f(x) = 2x
Start 1
1
Finish 1 1 1
1
• Replace every 1 with $
• Repeat:
3q
R$,
1
L,1
1
R,1
• Find rightmost $, replace it with 1
L,
$
R,1
• Go to right end, insert 1
2q
1q
Until no more $ remain
L,1
0q R, 3q
0q 1
49/49/5858
50/50/5858
TM compute succ(n) TM compute succ(n)
Another Example Another Example
if
x
y
1
The function is computable
yxf ,(
)
x
y
0
if
Turing Machine for
yx0
Input:
3q
1q
2q
or
1
T =
0
Output:
#|1, L 0|0, R
51/51/5858
52/52/5858
CCáác ngôn ng
c ngôn ngữữ đ đệệ quy v
quy vàà liliệệt kê đ
t kê đệệ quyquy
Turing Machine Pseudocode:
CCáác ngôn ng
nh đượợc bc bởởi mi mộột mt mááy Turing đư
y Turing đượợc gc gọọi i
• Repeat
c ngôn ngữữ xxáác đc địịnh đư (Recusive) llàà đđệệ quyquy (Recusive)
y x Match a 1 from with a 1 from
y Turing gọọi li làà
CCáác ngôn ng liliệệt kê đ
c ngôn ngữữ đư đượợc thc thừừa nha nhậận bn bởởi mi mộột mt mááy Turing g (Recursively Enumerable) t kê đệệ quyquy (Recursively Enumerable)
y
x
Until all of or is matched
TTừừ đ đóó ta cta cóó ccáác đc địịnh ngh
a sau : nh nghĩĩa sau :
MMộột ngôn ng
quy nếếu nu nóó đư đượợc xc xáác đc địịnhnh t ngôn ngữữ llàà đ đệệ quy n y Turing bbởởi mi mộột mt mááy Turing
x • If a 1 from is not matched
MMộột ngôn ng
erase tape, write 1
(
x
y
)
else
(
x
y
)
erase tape, write 0
t ngôn ngữữ llàà liliệệt kê đ t kê đệệ quy n quy nếếu nu nóó đư đượợc thc thừừa nha nhậậnn y Turing bbởởi mi mộột mt mááy Turing
53/53/5858
54/54/5858
9
LuLuậận đn đềề Turing
Church Turing--Church
NhNhậận xn xéét lut luậận đn đềề Turing
Church Turing--Church
Turing--Church đ
ng trong ng vai trò quan trọọng trong
LuLuậận đn đềề Turing
Turing--Church ph
Church pháát bi
u như sau :: t biểểu như sau
LuLuậận đn đềề Turing lý thuyếết tt tíính to lý thuy
Church đóóng vai trò quan tr n (Computability) nh toáán (Computability)
CCáác ngôn ng
LuLuậận đn đềề đưa ra l
i ta cóó ththểể phpháát bi
Turing -- t biểểu luu luậận đn đềề Turing
NgưNgườời ta c Church theo nghĩĩa ca củủa pha phéép tp tíính hnh hààm :m : Church theo ngh
CCáác hc hààm tm tíính đưnh đượợc bc bởởi mi mộột thu
1995) : nh: nhàà
c ngôn ngữữ đư đượợc nhc nhậận bin biếết bt bởởi mi mộột thu đưa ra lậập lup luậận rn rằằng mng mộột st sốố ngôn ng t thuậật t c ngôn ngữữ xxáác đc địịnh đưnh đượợc bc bởởi mi mộột t không thểể ngôn ngữữ không th n : thựực chc chấất lt làà hhìình th nh thứức c t thuậật tot toáán : th totoáán ln làà ccáác ngôn ng y Turing mmááy Turing
DDễễ ddààng mô ph
ng mô phỏỏng sng sựự hohoạạt đt độộng cng củủa ma mộột mt mááy Turing nh
Alonzo Church Alonzo Church (1903--1995) (1903 c ngườời Mi Mỹỹ ToToáán hn họọc ngư đã nghiên cứứu phu phéép p đã nghiên c ttíính hnh hààm m (Functional (Functional Calculus) vàà ttíính nh Calculus) v ttíính đư nh đượợc c (Computability) (Computability)
MMộột bt búút cht chìì vvàà ttờờ gigiấấy y MMộột chương tr
đưđượợc đoc đoáán nhn nhậận bn bởởi mi mộột thu nh toáánn i niệệm tm tíính to hhóóa kha kháái ni Turing--Church không ph LuLuậận đn đềề Turing nh lý, Church không phảải li làà mmộột đt địịnh lý, ng minh đượợcc nên không thểể chchứứng minh đư nên không th Church ááp dp dụụng mô h Turing--Church LuLuậận đn đềề Turing t thuậật tot toáán ln làà ccáác c y Turing hhààm tm tíính đnh đợợc bc bởởi mi mộột mt mááy Turing ng mô hìình lý thuy nh nghĩĩa cha chặặt cht chẽẽ đ đểể mô hmô hìình ho quan niệệm m Turing đượợc đc địịnh ngh Turing đư vvềề thuthuậật tot toáán ln làà khkháái ni i niệệm không đư m không đượợc xc xáác đc địịnh rõ r nh lý thuyếết lt làà mmááy y nh hoáá quan ni nh rõ rààngng y Turing nhờờ ::
t chương trìình ch nh chạạy trên m y trên mộột mt mááy ty tíính cnh cụụ ththểể
56/56/5858
55/55/5858
y Turing Xây dựựng mng mááy Turing Xây d
CCáác mc mááy Turing v
n năng y Turing vạạn năng
MMộột st sốố kkỹỹ thuthuậật xây d
y Turing t xây dựựng mng mááy Turing
y Turing MMộột vt vấấn đn đềề ththúú vvịị llàà liliệệu cu cóó ththểể ccóó mmộột mt mááy Turing
mô phmô phỏỏng đư
ng đượợc bc bấất kt kỳỳ mmááy Turing n
y Turing nàào ?o ?
ch tườờng minh, ta mu
ng minh, ta muốốn cung c
n cung cấấp cho m
p cho mộột mt mááy y
t câu vàào o ww nnàào đo đóó, m, mááy Turing M
y Turing M’’ bbấất kt kỳỳ nnàào đo đóó y Turing M’’ ccóó ththểể
Ghi nh MMởở rrộộng băng v MMááy Turing c MMááy Turing c
Ghi nhớớ ởở bbộộ đi điềều khi u khiểển hn hữữu hu hạạnn o vô hạạn vn vềề ccảả hai ph hai phííaa
MMộột ct cáách tư Turing M sựự mô tmô tảả ccủủa ma mộột mt mááy Turing M Turing M s sao cho vớới mi mộột câu v sao cho v mô phmô phỏỏng sng sựự đo đoáán nhn nhậận cn củủa M trên
a M trên ww
MMộột mt mááy Turing như v
y Turing như vậậy sy sẽẽ llàà mmộột st sựự nhnhạại li lạại ci cáác mc mááy y
n năng y Turing vạạn năng
Turing kháác, vc, vàà đư đượợc gc gọọi li làà mmááy Turing v Turing kh (Universal Turing Machine). (Universal Turing Machine).
ng băng vàào vô h y Turing cóó nhinhiềều băng u băng y Turing cóó bbộộ nhnhớớ truy c truy cậập trp trựực tic tiếếpp
57/57/5858
58/58/5858
10
