Luận văn Tìm hiểu về bài toán thứ mười của Hilbert

ô, ở mỗi thời điểm đầu đọc viết nhìn một ô trên 
băng. Các ký hiệu được ghi trên băng nằm trong một bảng chữ X nào đó, 
được gọi là bảng chữ của máy. Bộ phận điều khiển hoạt động như một ôtômát 
q 
Đầu đọc 
Băng 
Trạng thái 
 34 
hữu hạn, ở mỗi thời điểm nó có thể ở một trạng thái trong một tập hữu hạn Q 
các trạng thái của nó. Đầu đọc viết của máy có thể chuyển động trên băng 
sang trái hay sang phải. Máy được xem là hoạt động trong quá trình thời gian 
rời rạc. Bộ điều khiển có nhiệm vụ điều khiển toàn bộ quá trình hoạt động của 
máy. Quá trình này bao gồm nhiều bước cơ bản, mỗi bước cơ bản được thực 
hiện trong khoảng thời gian giữa hai thời điểm kế tiệp nhau. Mỗi bước cơ bản 
gồm các nội dung sau: ở thời điểm t tuỳ theo trạng thái q của bộ phận điều 
khiển và ký hiệu x mà đầu đọc-viết đọc được trên băng, máy sẽ ghi một ký 
hiệu x ' nào đó thay cho x, chuyển đầu đọc viết một ô sang trái hoặc sang phải, 
hoặc cũng có thể giữ đầu đọc viết đứng yên và bộ phận điều khiển sẽ chuyển 
sang một trạng thái q ' nào đó ở thời điểm t + 1. Các số liệu ban đầu được ghi 
trên băng trước khi máy bắt đầu hoạt động. Sau khi máy dừng hoạt động, ta 
cũng sẽ đọc kết quả trên băng. 
Định nghĩa 2.1.1. 
 Một máy Turing M là một bộ: 
  1, , ,M Q X q  
trong đó: 
 Q là một tập hữu hạn các trạng thái của M . 
 X là một bảng chữ hữu hạn không rỗng ( gọi là bảng chữ của máy). 
 1q Q là trạng thái ban đầu của máy. 
  là một ánh xạ từ tập con 'Q X   vào tập  ' , ,Q X L R N  , 
trong đó 
  'X X B  với B X 
 Ký hiệu B được gọi là ký hiệu rỗng. Ta quy ước một ô được ghi ký hiệu B 
tức là không có ký hiệu nào cả. Việc ghi B thay cho một ký hiệu x có nghĩa là 
xoá x. Các ký hiệu L, R, N chỉ các loại chuyển động của đầu đọc-viết trên 
 35 
băng: L có nghĩa là chuyển sang trái một ô, R có nghĩa là chuyển sang phải một 
ô, N có nghĩa là không chuyển động 
 Giả sử ',q Q x X  và  ,q x  . Khi đó    , ', ,q x q y d  cho ta một 
mệnh lệnh: nếu máy ở trạng thái q và nhìn ký hiệu x trên băng thì thay x bởi 
y, chuyển đầu đọc-viết sang trái một ô hoặc đứng yên tuỳ theo 
, hay Nd L R , và máy chuyển sang trạng thái 'q 
 Ánh xạ  thường được cho bởi một bảng gồm tất cả các từ dạng 
 'qxdyq (1) 
trong đó  ,q x  ,    ', , ,q y d q x . Một từ dạng (1) được gọi là một lệnh 
của máy. Một bảng lệnh của một máy Turing có tính chất là không thể có hai 
lệnh nào cùng có hai chữ đầu tương ứng giống nhau. 
 Khi có bảng lệnh của máy M, ta cũng xác định được các tập Q và X của nó. 
Do đó một máy Turing M hoàn toàn được xác định bởi một bảng lệnh và một 
trạng thái ban đầu. 
 Một từ dạng: 
 CqD 
trong đó *, C X' , D X'q Q    được gọi là một hình trạng của máy M. 
 Giả sử  và  là hai hình trạng của máy M. Ta nói máy M chuyển trực 
tiếp từ hình trạng  sang hình trạng  và viết 
 :M   ( hay   ) 
nếu xảy ra một trong các trường hợp sau: 
1) , 'CqxD Cq yD   và máy có lệnh 'qxNyq 
2) 1 2 2, 'Cqx x D Cyq x D   và máy có lệnh 1 'qx Ryq 
3) , 'Cqx Cyq B   và máy có lệnh 'qxRyq 
4) 1 2 1, 'Cx qx D Cq x yD   và máy có lệnh 2 'qx Lyq 
 36 
5) , 'qxD q ByD   và máy có lệnh 'qxLyq 
trong đó: 
B là ký hiệu rỗng, *, 'C D X ; , 'q q Q ; 1 2, , , 'x x x y X 
 Việc chuyển trực tiếp từ một hình trạng  sang một hình trạng  ứng với 
việc thực hiện một bước cơ bản của máy. 
 Ta nói máy M chuyển từ hình trạng  sang hình trạng  và viết 
 :M   ( hay   ) 
nếu có một dãy hình trạng 1 2, ,..., ( 1)k k       sao cho 1i i   với 
:1 1i i k    
 Từ định nghĩa ta luôn có   
 Một hình trạng CqxD  được gọi là hình trạng kết thúc nếu  ,q x  , 
tức là nếu máy M không có lệnh nào bắt đầu bởi qx 
 Hình trạng kết thúc tương ứng với việc máy dừng. 
 Khi máy chuyển từ  sang  và  là hình trạng kết thúc ta viết 
 :M   ( hay   ) 
 Giả sử Y là một bảng chữ sao cho X Y và *P Y . Khi đó ta sẽ ký hiệu 
X
P là từ thuộc X thu được bằg cách xoá trong P tất cả những chữ không 
thuộc X. 
 Giả sử M là máy Turing và *P X . Ta nói máy M thích dụng cho từ P và 
viết  !!M P , nếu có một hình trạng kết thúc  sao cho 
 1q P  ( hay 1q B  nếu P   ) 
 Nếu 
X
U  , thì ta nói M biến P thành U và viết  M P U 
 Máy M không thích dụng cho từ P nếu bắt đầu từ hình trạng 1q P ( hay 1q B 
nếu P   ) máy không chuyển đến một hình trạng kết thúc nào cả. 
 Khi M thích dụng cho P, quá trình máy chuyển từ hình trạng ban đầu 1q P 
 37 
dến hình trạng kết thúc  được gọi là một quá trình tính toán của máy M trên 
từ P. 
Ví dụ 2.1.2. 
Cho máy M với trạng thái ban đầu 1q và có bảng lệnh 
1 1 2 2
1 1 2 2
1 1 2 2
1 2
 q
 q
q BRBq q BNcq
q aRaq aNcq
q cRcq bNcq
q bLcq
Ta có 
 1 2 2q b q Bc q cc  do đó  M b cc 
 1 1 2q cb cq b q cc  do đó  M cb cc 
 1 1 1 1 ...q ca cq a caq B caBq B    
Máy M không thích dụng cho từ ca. 
Định nghĩa 2.1.3. Thuật toán là một máy Turing luôn luôn dừng. Một máy 
Turing có thể không phải luôn luôn dừng được gọi là thủ tục. 
2.2 Hàm đệ quy 
 Khái niệm hàm đệ quy cũng là một khái niệm toán học, nhằm chính xác hóa 
khái niệm hàm tính được theo nghĩa trực giác, do đó chính xác hóa hóa khái 
niệm thuật toán nói chung. Trước hết ta xét một lớp con đơn giản của lớp đó là 
lớp các hàm đệ qui nguyên thủy. 
2.2.1 Hàm đệ quy nguyên thủy 
 Giả sử  1,..., nf x x và  1,..., ng x x là hai hàm số n ngôi có thể không xác 
định khắp nơi. Ta ký hiệu 
  1,..., nf x x   1,..., ng x x 
để chỉ rằng với mọi  1,..., nx x nếu một trong hai vế xác định thì vế kia cũng 
 38 
 xác định và chúng có giá trị bằng nhau. 
 Giả sử  1,..., nf y y ,  1 1,..., ng x x ,,  1,...,m ng x x là các hàm số học có thể 
không xác định khắp nơi. Ta nói hàm  1,..., nh x x được xác định bởi phép hợp 
thành từ các hàm số 1; ,..., mf g g nếu 
       1 1 1 1,..., ,..., ,..., ,...,n n m nh x x f g x x g x x 
 Giả sử  1, ,..., nf y x x là một hàm số( có thể không xác định khắp nơi ). Ta 
nói hàm  1,..., nh x x là được xác định từ hàm  1, ,..., nf y x x bằng phép cực 
tiểu hoá, và viết 
     1 1,..., , ,..., 0n nh x x y f y x x  
nếu hàm h xác định tại  1,..., nx x khi và chỉ khi có số 0Y  sao cho dãy 
      1 1 10, ,..., , 1, ,..., ,..., , ,...,n n nf x x f x x f Y x x 
xác định, mỗi thành phần trong dãy đó đều khác 0, trừ thành phần cuối cùng 
  1, ,..., 0nf Y x x  
và khi đó  1,..., nh x x Y 
Định nghĩa 2.2.1 Giả sử cho hai hàm số ( có thể không xác định khắp nơi ): 
hàm n- ngôi  1,..., nf x x và hàm (n+2) – ngôi  1,..., , ,ng x x y z . Ta nói rằng 
hàm số  1,..., ,nh x x y được xác định từ các hàm f và g bởi phép đệ quy 
nguyên thuỷ, nếu với mọi số 1,..., ,nx x y ta có 
   
    
1 1
1 1 1
,..., ,0 ,...,
,..., , 1 ,..., , , ,..., ,
n n
n n n
h x x f x x
h x x y g x x y h x x y





Nhận xét 2.2.2. 
 Nếu hàm h không xác định tại  1,..., ,nx x a , thì nó cũng không xác định 
tại mọi  1,..., ,nx x y với y a 
 39 
 Nếu f và g xác định khắp nơi và h xác định từ f và g bằng phép đệ quy 
nguyên thuỷ, thì h cũng là hàm xác định khắp nơi. 
 Nếu 0n  thì f là hằng số và h là hàm của một đối số. 
Định nghĩa 2.2.3. Một hàm số f được gọi là hàm đệ quy nguyên thuỷ, nếu nó 
có thể thu được bằng một số hữu hạn lần dùng các phép hợp thành và phép đệ 
quy nguyên thuỷ, xuất phát từ các hàm sau: 
1)   1s x x  
2)   0N x  
3)  1,...,
n
i n iU x x x với mọi 1 n  và 1 i n  
Nhận xét 2.2.4. Vì các hàm    ,S x N x và  1,...,
n
i nU x x xác định khắp nơi 
và các hàm được xác định bằng phép hợp thành hay phép đệ quy nguyên thuỷ 
từ các hàm xác định khắp nơi cũng là xác định khắp nơi, do đó mọi hàm đệ 
quy nguyên thuỷ là xác định khắp nơi. 
Ví dụ 2.2.5. Các hàm sau đây là đệ quy nguyên thuỷ: 
1) x y vì 
1
10 ( )
( 1) ( )
x U x
x y S x y
  

   
2) .x y vì 
2
1
.0 ( )
.( 1) . ( , )
x N x
x y x y U x y


  
3) 
1, x 1
( )
0 , x=0
x
P x
 
 

 vì 
1
1
(0) 0
( 1) ( )
P
P x U x


 
4) x y vì 
0 0
( 1) ( )
x
x y P x y
 

   
 40 
5) 
1 nê 0
( )
0 nê 1
u x
sg x
u x

 

 vì ( ) 1sg x x  
6) 
0 nê 0
( )
1 nê 1
u x
sg x
u x

 

 vì ( ) 1 ( )sg x sg x  
7) Gọi rest(x,y) là phần dư của phép chia x cho y với quy ước rest(x,0) = x. 
Hàm rest(x,y) là hàm đệ quy nguyên thủy vì 
 es ( , ) ( .[ / ]).r t x y x y x y  
2.2.2 Hàm đệ quy bộ phận và hàm đệ quy 
Định nghĩa 2.2.6 Một hàm số  1,..., nf x x được gọi là hàm đệ quy bộ phận, 
nếu có thể thu được từ các hàm 
1)   1s x x  
2)   0N x  
3)  1,...,
n
i n iU x x x với mọi 1 n  và 1 i n  
bằng cách dùng một số hữu hạn lần các phép hợp thành, phép đệ quy nguyên 
thuỷ và phép cực tiểu hoá. 
 Hàm số  1,..., ,nf x x y được gọi chính quy, nếu hàm 
   1,..., , 0ny f x x y  
xác định khắp nơi, nghĩa là với mọi  1,..., nx x có số 0Y  sao cho dãy 
      1 1 1,..., ,0 , ,..., ,1 ,..., ,..., ,n n nf x x f x x f x x Y 
là xác định, mỗi thành phần đều khác không, trừ thành phần cuối cùng bằng 0. 
Định nghĩa 2.2.7 Một hàm số  1,..., nf x x được gọi là hàm đệ quy toàn phần 
(hay gọi tắt là hàm đệ quy), nếu có thể thu được từ các hàm    ,S x N x và 
 1,...,
n
i nU x x bằng cách dùng một số hữu hạn lần các phép hợp thành, phép đệ 
 41 
quy nguyên thuỷ và phép cực tiểu hoá, trong đó phép cực tiểu hoá chỉ dùng 
cho các hàm chính quy. 
Nhận xét 2.2.8. Từ định nghĩa suy ra: 
1) Mọi hàm đệ quy nguyên thuỷ đều là hàm đệ quy. 
2) Mọi hàm đệ quy đều là hàm đệ quy bộ phận và xác định khắp nơi. 
3) Một hàm đệ quy bộ phận là hàm đệ quy khi và chỉ khi nó xác định khắp 
nơi. 
4) Có những hàm đệ quy bộ phận nhưng không đệ quy. Ví dụ hàm 
  ( ) 2 0f x y x y   
là hàm đệ quy bộ phận, nhưng không đệ quy vì nó không xác định khi x là 
số lẻ. 
2.3 Các tập hợp và các tân từ đệ quy, đệ quy kể được 
2.3.1 Các tập hợp và các tân từ đệ quy 
Định nghĩa 2.3.1. Một tân từ n ngôi  1,..., nP x x là một phán đoán phụ thuộc 
vào các số 1,..., nx x , nó có thể là đúng hay sai với mỗi bộ các số  1,..., nx x . 
 Một tập hợp số E có thể được xem là một tân từ một ngôi, nếu ta đồng nhất 
E với tân từ x E , hay viết ( )E x . 
 Hàm 1( ,..., )P nx x được gọi là hàm đặc trưng của tân từ 1( ,..., )nP x x , nếu 
với mọi 1,..., nx x ta có: 
1
0
( ,..., )
1
P nx x

 

 
nếu 1( ,..., ) ng nP x x đú 
nếu 1( ,..., ) nP x x sai 
Ví dụ: Hàm ( )sg x là hàm đặc trưng của tập hợp  0 . 
Định nghĩa 2.3.2. Tân từ  1,..., nP x x được gọi là tân từ đệ quy (hay đệ quy 
nguyên thủy), nếu hàm đặc trưng 1( ,..., )P nx x của nó là hàm đệ quy (hay đệ 
 42 
quy nguyên thủy). 
 Tập hợp E là đệ quy (đệ quy nguyên thủy), nếu tân từ x E là đệ quy (đệ 
quy nguyên thủy). 
 Tân từ  1,..., nP x x được gọi là tân từ đệ quy kể được, nếu tập hợp 
 {    1 1,..., ,...,n nx x P x x đúng } 
là miền xác định của một hàm đệ quy bộ phận nào đó. 
 Ta sẽ dùng các ký hiệu liên kết logic & (và),  (hay là), (không), x (với 
mọi x) và x (có x) để lập các tân từ phức tạp từ các tân từ cho trước. Cho các 
tân từ 1( ,..., )nP x x và 1( ,..., )nQ x x . Tân từ 1( ,..., )nP x x & 1( ,..., )nQ x x được xem 
là đúng khi và chỉ khi cả 1( ,..., )nP x x và 1( ,..., )nQ x x đều đúng. Tân từ 
1( ,..., )nP x x  1( ,..., )nQ x x được xem là đúng khi và chỉ khi ít nhất một trong 
hai tân từ 1( ,..., )nP x x và 1( ,..., )nQ x x là đúng. Tân từ 1( ,..., )nP x x đúng khi và 
chỉ khi 1( ,..., )nP x x sai. Tân từ 1( , ,..., )nyP y x x đúng khi và chỉ khi với mọi số 
y 1( , ,..., )nP y x x là đúng. Tân từ 1( , ,..., )nyP y x x đúng khi và chỉ khi có số y 
sao cho 1( , ,..., )nP y x x là đúng. Tương tự tân từ 1 ( ( , ,..., ))ny y z P y x x   là 
đúng với 1( , ,..., )nz x x khi và chỉ khi với mọi số y z 1( , ,..., )nP y x x là đúng, 
v.v 
Định lý 2.3.3. Nếu 1( ,..., )nP x x và 1( ,..., )nQ x x là các tân từ đệ quy nguyên 
thủy, thì các tân từ 1( ,..., )nP x x & 1( ,..., )nQ x x , 1( ,..., )nP x x  1( ,..., )nQ x x và 
1( ,..., )nP x x cũng là đệ quy nguyên thủy. 
Chứng minh: Gọi P và Q là các hàm đặc trưng của các tân từ P và Q. Khi 
 đó các hàm đặc trưng &P Q , P Q và P của các tân từ & , ,P Q P Q và P 
 được xác định bởi 
 & 1 1 1( ,..., ) ( ( ,..., ) ( ,..., ))P Q n P n Q nx x sg x x x x     
 43 
 1 1 1( ,..., ) ( ,..., ). ( ,..., )P Q n P n Q nx x x x x x    
 1 1( ,..., ) ( ( ,..., ))n P nP x x sg x x   
Vì P và Q là các hàm đệ quy nguyên thủy, nên các hàm &P Q , P Q và P 
cũng là đệ quy nguyên thủy. 
Định lý 2.3.4. Nếu 1( , ,..., )nP y x x là tân từ đệ quy nguyên thủy, thì các tân từ 
    1 1, ,..., ( , ,..., )n nQ z x x y y z P y x x   
    1 1, ,..., & ( , ,..., )n nR z x x y y z P y x x   
cũng là đệ quy nguyên thủy. 
Chứng minh: Giả sử P là hàm đặc trưng của tân từ P. Khi đó hàm đặc trưng 
Q và R của các tân từ Q và R được xác định bởi 
  1 1
0
, ,..., ( , ,..., )
z
Q n P n
y
z x x sg y x x

 
  
 
  
  1 1
0
, ,..., ( , ,..., )
z
R n P n
y
z x x y x x

  
Vì P là đệ quy nguyên thủy nên các hàm Q và R cũng là đệ quy nguyên 
thủy. 
Định lý 2.3.5. Nếu 1( ,..., )mP y y là tân từ đệ quy nguyên thủy và 
1 1( ,..., ),ng x x , 1( ,..., )m ng x x là các hàm đệ quy nguyên thủy, thì tân từ 
    1 1 1 1,..., ( ,..., ),..., ( ,..., )n n m nQ x x P g x x g x x 
cũng là đệ quy nguyên thủy. 
Chứng minh: Hàm đặc trưng được xác định bởi 
    1 1 1 1,..., ( ,..., ),..., ( ,..., )Q n P n m nx x g x x g x x  
Từ đó ta suy ra điều phải chứng minh. 
 44 
Định lý 2.3.6. Nếu 1( , ,..., )nP y x x là tân từ đệ quy, thì tân từ 
    1 1,..., , ,...,n nR x x yP y x x  là đệ quy kể được. 
Chứng minh: Tập hợp các 1( ,..., )nx x làm cho  1,..., nR x x đúng trùng với 
miền xác định của hàm đệ quy bộ phận sau: 
    1 1,..., ( , ,..., ) 0n P nf x x y y x x    . 
Do đó theo định nghĩa của hàm đệ quy kể được ta có điều phải chứng minh.  
2.3.2 Các tập hợp và các tân từ đệ quy kể được 
Định nghĩa 2.3.7. Tân từ  1,..., nP x x được gọi là tân từ đệ quy kể được, nếu 
tập hợp 
 {    1 1,..., ,...,n nx x P x x đúng } 
là miền xác định của một hàm đệ quy bộ phận nào đó. 
Nhận xét 2.3.8. Từ các định nghĩa ở trên ta suy ra: 
 Mọi tân từ đệ quy nguyên thủy là tân từ đệ quy. 
 Mọi tân từ đệ quy là tân từ đệ quy kể được. Thât vậy, nếu  1,..., nP x x là 
tân từ đệ quy và P là hàm đặc trưng của nó, thì hàm 
     1 1,..., ,..., 0n P nf x x y x x y    
 xác đinh khi và chỉ khi  1,..., nP x x đúng. Hàm f là đệ quy bộ phận, do 
đó  1,..., nP x x là tân từ đệ quy kể được. 
Định lý 2.3.9. Với mọi tân từ đệ quy kể được  1,..., nP x x có một tân từ đệ quy 
nguyên thủy  1, ,..., nR y x x sao cho    1 1,..., , ,...,n nP x x yR y x x  . 
Chứng minh: 
 Giả sử tập hợp {    1 1,..., ,...,n nx x P x x đúng } là miền xác định của hàm đệ 
quy bộ phận  1,..., nf x x . Khi đó có số e sao cho 
 45 
  1 1,..., ( ( , ,..., , ))n n nf x x U yT e x x y  
Rõ ràng  1,..., nf x x xác định khi và chỉ khi 1( , ,..., , )n nyT e x x y . Vậy 
  1 1,..., ( , ,..., , )n n nP x x yT e x x y  
Tân từ 1( , ,..., , )n nT e x x y là đệ quy nguyên thủy. Định lý được chứng minh.  
Định lý 2.3.10. 1) Nếu các tân từ  1 1,..., nP x x và  2 1,..., nP x x là đệ quy kể 
được, thì các tân từ 
      1 1 1 1 2 1,..., ,..., & ,...,n n nS x x P x x P x x 
      2 1 1 1 2 1,..., ,..., ,...,n n nS x x P x x P x x  
cũng là đệ quy kể được. 
 2) Nếu tân từ  1, ,..., nP y x x là đệ quy kể được, thì các tân từ 
    1 1 1,..., , ,...,n nV x x yP y x x  
    2 1 1, ,..., , ,...,n nV z x x y zP y x x  
cũng là đệ quy kể được. 
Chứng minh: 1) Theo định lý 2.3.5. có các tân từ đệ quy nguyên thủy 
 1 1, ,..., nR y x x và  2 1, ,..., nR y x x sao cho 
    1 1 1 1,..., , ,...,n nP x x yR y x x  
    2 1 2 1,..., , ,...,n nP x x yR y x x  
Do đó ta dễ thấy rằng 
     1 1 1 1 2 1
1 1 2 1
,..., , ,..., & , ,...,
 u ( ( ), ,..., ) & ( ( ), ,..., )
n n n
n n
S x x yR y x x yR y x x
R K u x x R L u x x
  
 
     2 1 1 1 2 1
1 1 2 1
,..., , ,..., , ,...,
 ( ( , ,..., ) ( , ,..., ))
n n n
n n
S x x yR y x x yR y x x
y R y x x R y x x
   
  
trong đó K và L là các hàm đệ quy nguyên thủy. Theo định lý 2.3.6 các tân từ 
 46 
1 1 2 1( ( ), ,..., ) & ( ( ), ,..., )n nR K u x x R L u x x và 1 1 2 1( , ,..., ) ( , ,..., )n nR y x x R y x x là 
đệ quy nguyên thủy. Do đó theo định lý 2.3.4. 1S và 2S là đệ quy kể được. 
 2) Có tân từ đệ quy nguyên thủy  1, , ,..., nR u y x x sao cho 
    1 1, ,..., , , ,...,n nP y x x uR u y x x  
Do đó ta có 
   1 1 1
1
,..., , , ,...,
 ( ( ), ( ), ,..., )
n n
n
V x x y uR u y x x
tR K t L t x x
  
 
   2 1 1
1
, ,..., , , ,...,
 ( ( , ), , ,..., )
n n
n
V z x x y z uR u y x x
t y zR G t y y x x
  
   
trong đó G là hàm đệ quy nguyên thủy. Theo các định lý 2.3.4 và 2.3.5 các 
tân từ 1( ( ), ( ), ,..., )nR K t L t x x và 1( ( , ), , ,..., )ny zR G t y y x x  
đều là đệ quy nguyên thủy. Từ đó theo định lý 2.3.6, các tân từ 1V và 2V là đệ 
quy kể được.  
Định lý 2.3.11. Miền giá trị của mọi hàm tính được bộ phận  1,..., nf x x , tức 
là tập 
   1 1,..., ( ,..., )n nE y x x f x x y    
là một tập đệ quy kể được. 
Chứng minh: Hàm  1,..., nf x x là đệ quy kể được, do đó có số e sao cho 
  1 1,..., ( ( , ,..., , ))n n nf x x U yT e x x y  
Do đó 
 1 1,..., , ( ( , ,..., , ) & ( ) )n n nx E x x y T e x x y U y u      
Tân từ trong dấu ngoặc là đệ quy nguyên thủy. Từ đó theo phần 2) của định lý 
2.3.10, E là tập đệ quy kể được.  
 47 
2.4 Tính chất các tập và các ngôn ngữ đệ quy, đệ quy kể được 
 Ta sẽ xét một số kết quả về tính chất của các tập và ngôn ngữ đệ quy, đệ quy 
kể được như sau: 
Định lý 2.4.1. Một ngôn ngữ là đệ quy kể được nếu nó được chấp nhận bởi 
một máy Turing nào đó. 
Chứng minh: Cho L với L = L(M), với M là một máy Turing nào đó, ta xây 
dựng một văn phạm G sao cho L = L(G) như sau: chữ bắt đầu của G sinh một 
từ bất kỳ xuất hiện trên băng được bao bởi ký hiệu đánh dấu biên # và chứa 
thêm một xuất hiện của trạng thái kết thúc. Phần chính của các sản xuất gồm 
các sản xuất của M với hai vế đổi chỗ cho nhau. Cuối cùng các ký hiệu đánh 
dấu biên và ký hiệu trạng thái bị khử đi bởi các sản xuất 0#q  và #  . 
Ngược lại, cho L = L(G), ta dùng luận đề Church để tìm một máy Turing M 
sao cho L = L(G). Điều đó suy ra vì rõ ràng G cho một thủ tục hiệu quả để liệt 
kê mọi từ của L.  
Định nghĩa 2.4.2. Một tập S các số nguyên không âm là đệ quy kể được nếu S 
bằng miền xác định của một hàm đệ quy bộ phận một biến. S là đệ quy nếu 
hàm đặc trưng của nó đệ quy. 
 Kí hiệu m-adic, với m 2 được dựa trên các từ trên bộ chữ cái  1,2,...,n . 
Một từ cụ thể 1 2... na a a mà mỗi ia là một chữ ký hiệu một số nguyên 
 1 21 2 1...
k k
k ka n a n a n a
 
    
 Mỗi ngôn ngữ  
*
1,..., mL a a có thể được xem như một tập các số nguyên 
không âm bằng cách xét các từ như các số nguyên ở ký hiệu m-adic. 
 Ký hiệu N(L) là tập các số nguyên kết hợp với L theo cách này. Chẳng hạn, 
nếu  
*
1 2,L a a là ngôn ngữ được ký hiệu bởi biểu thức chính quy 
 48 
 
*
1 2 1a a a thì N(L) bằng tập mọi số nguyên lẻ.Nếu  
*
1 2,L a a là ngôn 
ngữ được ký hiệu bởi biểu thức chính quy  
*
1 2a a thì 
  ( ) 2 1nN L n  . 
Định lý 2.4.4. Nếu ngôn ngữ L là đệ quy kể được (tương ứng đệ quy) thì N(L) 
cũng đệ quy kể được ( tương ứng đệ quy). 
Ta có mệnh đề đảo của định lý 2.5.5 
 Định lý 2.4.5. Nếu một tập N các số nguyên không là đệ quy kể được (tương 
ứng đệ quy), thì một ngôn ngữ L bất kỳ sao cho N = N(L) cũng là đệ quy