An toàn thông tin – Nhóm 14 – Turing
Giới thiệu về turing
Turing (đặt theo tên của Alan Turing) là một thuật toán nghiên cứu mã hóa
dòng thiết kế. Đặc điểm:
- Xử lý nhanh.
- Sử dụng ít bộ nhớ trên bộ xử lý nhúng.
- Khai thác song song.
Turing được thiết kế để đáp ứng nhu cầu của các ứng dụng nhúng như giọng
nói mã hóa trong máy điện thoại không dây, ….
Turing có bốn thành phần:
- Trọng tải
- Khởi động
- LFSR
- Một khóa tuyến tính không lọc.
Hình 1: Các thành phần của mật mã dòng turing
I. Máy turing và thuật toán
Thành viên: Đào Thị Thanh Dung – Phương Ngọc Hoa
1
An toàn thông tin – Nhóm 14 – Turing
Máy Turing có một băng nhớ, dùng để ghi mọi loại dữ liệu (dữ liệu nhập,
dữ liệu dùng cho việc điều khiển tương tự như một chương trình máy tính và
các kết quả trung gian khi làm việc). Với một bộ điều khiển chứa một số hữu
hạn trạng thái, TM cũng như các ôtômát khác, làm việc theo lối "ngắt quãng"
theo từng bước chuyển.
1. Mô tả về máy Turing
Máy Turing có rất nhiều mô hình và định nghĩa khác nhau nhưng tất cả
chúng đều tương đương nhau. Mô hình cơ bản của một máy Turing gồm :
- Một bộ điều khiển hữu hạn.
- Một băng được chia thành các ô.
- Một đầu đọc-viết, mỗi lần đọc có thể duyệt qua một ô trên băng để đọc
hay viết ký hiệu.

• Cứ mỗi bước trong quá trình thực hiện (xem hình), máy sẽ
thực hiện:
o Đọc ký hiệu đối diện đầu đọc,
o Thay ký hiệu đó bằng ký hiệu tính được từ hàm dịch chuyển,
o Dời đầu đọc một ô sang trái hay sang phải theo hướng chỉ định
bởi hàm dịch chuyển,
Thành viên: Đào Thị Thanh Dung – Phương Ngọc Hoa
3
An toàn thông tin – Nhóm 14 – Turing
o Đổi trạng thái hiện tại thành trạng thái tiếp theo, cho bởi hàm
dịch chuyển.
Xâu vào là được thừa nhận khi quá trình thực hiện đối với xâu đó đạt
đến một trạng thái thừa nhận
Hinh 3:
2. Định nghĩa về máy turing
Một cách hình thức, ta định nghĩa một máy Turing (TM) như sau :
Định nghĩa: TM là một hệ thống M (Q, Σ, Γ, δ, q
0
, B, F), trong đó:
. 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ý tự được phép viết trên băng.
. B : ký hiệu thuộc Γ dùng chỉ khoảng trống trên băng (Blank).
. δ : hàm chuyển ánh xạ : Q × Γ → Q × Γ × {L, R, ∅}
(δ có thể không xác định với một vài đối số)
. q
0
∈
Q là trạng thái bắt đầu
. F

,
δ
, q
0
, F> với các thành phần :
Q = {q
0
, q
1
, q
2
, q
3
, q
4
}; ∑= {0, 1}; Γ = {0, 1, X, Y, B} và F = {q
4
}.
Ta có thể hình dung mỗi trạng thái là một câu lệnh hoặc một nhóm các câu
lệnh trong chương trình. Trạng thái q
0
là trạng thái khởi đầu và nó làm cho ký
hiệu 0 bên trái nhất thay bằng X. Trạng thái q
1
được dùng để tiến sang phải bỏ
qua các số 0 và Y để tìm 1 bên trái nhất. Nếu M tìm thấy 1 nó thay 1 bằng Y rồi
đi vào trạng thái q
2
. Trạng thái q
2

4
(trạng thái kết thúc) để chấp nhận
input. Ngược lại input bị loại bỏ.
Ta có hàm chuyển δ được cho trong bảng sau :
Hình 4. Một máy Turing kiểm nhận {0
n
1
n
| n>=1}
Các phép chuyển hình thái của máy Turing M trên input 0011 :
q
0
0011 ⊢ Xq
1
011 ⊢ X0q
1
11 ⊢ X q
2
0Y1 ⊢ q
2
X0Y1 ⊢ X q
0
0Y1 ⊢
XXq
1
Y1 ⊢ XXY q
1
1 ⊢ XX q
2
YY ⊢ X q

bằng từ “start” và một mũi tên đi vào trạng thái đó. Kiểm trạng được chi ra bằng
vòng kép. Vì thế thông tin duy nhất của máy Turing không đọc trực tiếp được từ
sơ đồ là ký hiệu được dùng cho ô trống. Chúng ta sẽ xem như đó là B trừ khi
được nói rõ.
Ví dụ: sơ đồ chuyển vị của một máy turing
4. Máy turing biểu diễn thuật toán
Máy Turing là một thành phần rất quan trọng trong nền khoa học của thế kỷ
XX, một phần vì máy Turing đóng vai trò trung tâm trong lý thuyết về tính toán
và khả năng tính toán. Đặc biệt, máy Turing không chỉ được quan tâm như là một
bộ chấp nhận ngôn ngữ mà còn cung cấp một định nghĩa nghiêm ngặt về thuộc
tính hay phương pháp.
Các thuật toán rất cần thiết cho máy tính xử lý thông tin
Thông thường, khi một thuật toán được kết hợp với thông tin xử lý, dữ liệu
được đọc từ một nguồn hay thiết bị đầu vào, được viết trên một thiết bị đầu ra,
và/hoặc được lưu trữ cho các xử lý tiếp sau. Trong khi đó, một máy Turing có thể
được biểu diễn như một hệ thống thực hiện chức năng tự động có khả năng ở một
số hữu hạn các trạng thái bên trong và được hỗ trợ bởi một bộ nhớ bên ngoài vô
hạn, gọi là băng (nhập/xuất).
Thành viên: Đào Thị Thanh Dung – Phương Ngọc Hoa
7
An toàn thông tin – Nhóm 14 – Turing
Khái niệm máy Turing có thể được sử dụng để đảm bảo mô hình hóa ý tưởng
tổng quát của một thuật toán được chính xác với một bảng chữ cái đã cho như
sau:
• Input của một sự tính toán là tất cả các kí hiệu không trắng
trên băng tại thời điểm khởi đầu.
• Tại thời điểm kết thúc của sự tính toán, output sẽ là bất kì cái
gì có trên băng.
• Vậy có thể xem một máy Turing M như là một sự hiện thực
của một hàm f được định nghĩa bởi = f(w) trong đó q

cặp chữ số nhị phân với nhau (có nhớ) để tính tổng của hai số nguyên.
Để cộng a và b, trước hết cộng hai bit ở phải cùng của chúng, tức là:
a
0
+ b
0
= c
0
.2 + s
0
.
Ở đây s
0
là bit phải cùng trong khai triển nhị phân của a+b, c
0
là số nhớ, nó có
thể bằng 0 hoặc 1. Sau đó ta cộng hai bit tiếp theo và số nhớ
Thành viên: Đào Thị Thanh Dung – Phương Ngọc Hoa
8
An toàn thông tin – Nhóm 14 – Turing
a
1
+ b
1
+ c
0
= c
1
.2 + s
1

s
1
s
0
)
2
.
Triển khai thuật toán này với máy Turing, chúng ta phải quyết định các số x và
y vào lúc ban đầu được đặt như thế nào trên băng và tổng của chúng xuất hiện
như thế nào lúc kết thúc sự tính toán.
• Chúng ta giả thiết rằng w(x) và w(y) được phân cách bằng một
kí hiệu  , với đầu đọc ở trên kí tự phải cùng của w(y).
• Chúng ta vì vậy muốn thiết kế một máy Turing để thực hiện
sự tính toán (trong đó q
f
là một trạng thái kết thúc)
q
0
w(x) w(y)
M
q
f
w(x + y) ,
Q = {q0, q1, q2, q3,…., q9, q
f
}, F = {q
f
}
Với bảng trạng thái được cho bởi đồ thị trạng thái như sau:
Thành viên: Đào Thị Thanh Dung – Phương Ngọc Hoa

• Các mô hình thay thế khác có thể được đưa ra cho sự tính toán
cơ học nhưng không có cái nào trong số chúng là mạnh hơn mô hình
máy Turing.
Bằng việc chấp nhận luận đề Turing, chúng ta sẵn sàng để định nghĩa chính
xác khái niệm thuật toán, một khái niệm cơ bản trong khoa học máy tính.
Thành viên: Đào Thị Thanh Dung – Phương Ngọc Hoa
11
An toàn thông tin – Nhóm 14 – Turing
Một thuật toán cho một hàm f: D → R là một máy Turing M sao cho cho
một chuỗi nhập w∈D trên băng nhập, cuối cùng M dừng với kết quả f(w) ∈R trên
băng. Một cách cụ thể là:
q
0
w
M
q
f
f(w), q
f
∈F, ∀w ∈ D.
5. Ngôn ngữ và hàm tính được
Ngôn ngữ được chấp nhận bởi máy turing là ngôn ngữ đệ quy liệt kê
Máy Turing như là một máy tính hàm số nguyên
II. Một số kỹ thuật xây dựng máy turing
1. Lưu trữ trong bộ điều khiển (Storage in the finite control)
Bộ điều khiển có thể dùng để lưu trữ một lượng hữu hạn thông tin.
Ví dụ: Xét máy Turing M nhận vào ký hiệu đầu tiên trên chuỗi nhập (viết trên
bộ chữ ái {0, 1}), lưu trữ vào bộ điều khiển và kiểm tra rằng ký hiệu này không,
có xuất hiện ở vị trí nào khác trên chuỗi nữa hay không ?
LG:

δ([q
0
, B], 1) = ([q
1
, 1], 1, R)
Bắt đầu từ trạng thái [q
0
, B], TM đọc và lưu trữ ký hiệu đầu tiên trên băng vào
thành phần thứ 2 trong bộ điều khiển.
2) δ([q
1
, 0], 1) = ([q
1
, 0], 1, R)
δ([q
1
, 1], 0) = ([q
1
, 1], 0,
Thành viên: Đào Thị Thanh Dung – Phương Ngọc Hoa
12
An toàn thông tin – Nhóm 14 – Turing
Nếu các ký hiệu được đọc tiếp theo không giống với ký hiệu đang lưu trữ thì
tiếp tục chuyển sang phải
3) δ([q
1
, 0], B) = ([q
1
, B], 0, ∅)
δ([q

nhập. Ký hiệu Blank là [B, B, B].
Viết số 2 dạng nhị phân trên rãnh 2 (tức 10)
Chép rãnh 1 vào rãnh 3 sau đó lấy rãnh 3 trừ rãnh 2 nhiều lần nhất có thể được
(thực hiện việc chia số cần kiểm tra cho số trên rãnh 2, lấy phần dư)
Thành viên: Đào Thị Thanh Dung – Phương Ngọc Hoa
13
An toàn thông tin – Nhóm 14 – Turing
Xét số còn lại (số dư) :
- Nếu số còn lại là 0 thì input không là số nguyên tố (vì nó chia hết cho số trên
rãnh 2)
- Nếu số còn lại khác 0 thì tăng số trên rãnh 2 thêm một đơn vị: nếu số trên
rãnh 2 bằng số trên rãnh 1 (số n) thì input n là số nguyên tố vì n đã không chia hết
cho bất kỳ số nào từ 2 đến n -1. Nếu số trên rãnh 2 nhỏ hơn số trên rãnh 1 thì ta
lặp lại quá trình trên với số mới trên rãnh 2.
Hình trên mô tả một TM với k = 3, kiểm tra số n = 47 viết trên rãnh 1 dưới
dạng nhị phân, TM đang thực hiện phép chia 47 cho 5. Nó đã trừ 2 lần số 5 vào số
47, vậy ở rãnh 3 hiện đang có số 37.
3. Đánh dấu ký hiệu (Checking off symbols)
Kỹ thuật đánh dấu thường dùng để nhận diện các ngôn ngữ được định nghĩa
bằng cách lặp lại chuỗi chẳng hạn như {ww | w
∈
Σ
*
}; {wcy | w, y
∈
Σ
*
, w ≠ y}
hoặc {ww
R

trình bao gồm thủ tục đệ qui hoặc có tham số. Ý tưởng chung là ta viết một phần
chương trình của TM như là một chương trình con. Nó sẽ được thiết kế có chứa
một trạng thái khởi đầu và một trạng thái trở về, trạng thái trở về là trạng thái
không có phép chuyển kế tiếp và nó sẽ đóng vai trò là trạng thái khởi đầu của một
TM khác hoặc là một trạng thái nào đó trong một TM khác. Nghĩa là từ trạng thái
trở về của TM này ta tiếp tục các phép chuyển của một TM khác, sự kiện này có ý
nghĩa như là gọi một chương trình con khác hoặc tiếp tục thực hiện chương trình
cấp trên. Lưu ý, các trạng thái của chương trình con phải phân biệt với chương
trình cấp trên của nó.
III. Một số biến dạng của máy turing
1. Máy Turing với băng vô hạn 2 chiều
Máy Turing với băng vô hạn hai chiều cũng tương tự như mô hình gốc (TM vô
hạn một chiều băng), chỉ khác là băng của nó không có cận trái như mô hình gốc,
nghĩa là ta xem như TM có vô hạn Blank ở cả hai đầu băng. Vì thế hàm δ được
mở rộng thêm bằng cách xét thêm các trường hợp đặc biệt tại cận trái như sau :
Nếu δ(q, X) = (p, Y, L) thì qXα ⊢ pBYα
Nếu δ(q, X) = (p, B, R) thì qXα ⊢ pα
Định lý 7.1 : Nếu L được nhận diện bởi TM với băng vô hạn hai chiều thì L
cũng được nhận diện bằng TM vô hạn một chiều băng
2. Máy Turing với nhiều băng vô hạn hai chiều
Xét máy Turing có một bộ điều khiển có k đầu đọc và k băng vô hạn hai
chiều. Mỗi phép chuyển của máy Turing, phụ thuộc vào trạng thái của bộ điều
khiển và ký tự đọc được tại mỗi đầu đọc, nó có thể thực hiện các bước sau :
Thành viên: Đào Thị Thanh Dung – Phương Ngọc Hoa
15
An toàn thông tin – Nhóm 14 – Turing
1) Chuyển trạng thái.
2) In ký hiệu mới tại mỗi đầu đọc để thay thế ký hiệu vừa đọc.
3) Đầu đọc có thể giữ nguyên vị trí hoặc dịch trái hoặc dịch phải 1 ô một cách
độc lập nhau.

Turing phụ thuộc vào trạng thái và các ký tự được đọc bởi mỗi đầu băng. Mỗi đầu
dịch chuyển một cách độc lập sang trái, sang phải hoặc đứng yên.
Thành viên: Đào Thị Thanh Dung – Phương Ngọc Hoa
16
An toàn thông tin – Nhóm 14 – Turing
Định lý 7.5 : Nếu L được chấp nhận bởi máy Turing k đầu đọc M
1
thì L cũng
được chấp nhận bởi một máy Turing một đầu đọc M
2
nào đó.
Thành viên: Đào Thị Thanh Dung – Phương Ngọc Hoa
17