ĐẠI HỌC ĐÀ NẴNG
TRƯỜNG ĐẠI HỌC BÁCH KHOA

KHOA CÔNG NGHỆ THÔNG TIN

GIÁO TRÌNH
LÝ THUYẾT
TÍNH TOÁN

PGS.TS. PHAN HUY KHÁNH
ĐÀ NẴNG 1999


PGS.TS. PHAN HUY KHÁNH biên soạn 1

MỤC LỤC

CHƯƠNG 1 NHẬP MÔN LÝ THUYẾT TÍNH TOÁN 1
I. CÁC ĐỐI TƯỢNG ĐƯỢC XỬ LÝ TRONG TIN HỌC 1
II. CÁC MÁY (MACHINES) 2
II.1. Khía cạnh chức năng (functional look) 2
II.2. Khía cạnh cấu trúc (structural look) 3
III. MÔ HÌNH TÍNH TOÁN 4

III.5. Lập trình trên ngôn ngữ bậc cao máy Turing 37
III.4.1. Cấu trúc if then else và cấu trúc rẽ nhiều nhánh 37
III.4.2. Cấu trúc while 38
III.6. Quản lý bộ nhớ 39
III.5.1. Máy Turing chuyển một ô qua phải 39
2 Lý thuyết tính toán
III.5.2. Máy Turing chỉ sử dụng phần băng bên phải
kể từ vị trí đầu tiên của đầu đọc-ghi 39
III.7. Một số máy Turing thông dụng 40
III.6.1. Sao chép 40
III.6.2. Kiểm tra bằng nhau 41
III.6.3. Liệt kê các câu, các cặp câu và dãy các câu 41
III.6.4. Các hàm chiếu ngược (antiprojection function) 42
III.6.5. Các hàm giao hoán 42

III.7. Các hàm T-tính được phức tạp hơn 42
III.8. Nhận xét 43
IV. CÁC BIẾN THẾ KHÁC CỦA MÔ HÌNH MÁY TURING 46
IV.1. Mô phỏng một máy Turing bởi một máy khác 46
IV.2. Các biến thể của máy Turing 48
IV.2.1. Máy Turing có k băng 48
IV.2.2. Các máy off−line và các máy có băng ra 49
IV.2.3. Các máy Turing không đơn định 49
IV.2.4. Thu gọn một bảng chữ còn ba ký tự 50
IV.2.5. Rút gọn một bảng chữ còn hai ký tự 52

IV.3. Các máy Turing có băng vô hạn một phía 52
V. MÁY TURING VẠN NĂNG 53
VI. TỒN TẠI CÁC HÀM KHÔNG LÀ T−TÍNH ĐƯỢC 55
CHƯƠNG 4 LUẬN ĐỀ CHURCH 59

−
tính được 70
II.3.1. Sơ đồ hợp thành tổng quát 70
II.3.2. Sơ đồ đệ quy đơn 70
II.3.3. Sơ đồ tối thiểu 71
Nhập môn lý thuyết tính toán 3

II.4. Mọi hàm T
−
tính được là đệ quy bộ phận 71
III. LUẬN ĐỀ CHURCH 73
CHƯƠNG 5 CÁC BÀI TOÁN KHÔNG QUYẾT ĐỊNH ĐƯỢC 77
I. CÁC NGÔN NGỮ LIỆT KÊ ĐỆ QUY VÀ CÁC NGÔN NGỮ ĐỆ QUY 77
II. CÁC BÀI TOÁN KHÔNG QUYẾT ĐịNH ĐƯỢC 82
III. THUẬT TOÁN RÚT GỌN MỘT BÀI TOÁN VỀ BÀI TOÁN KHÁC 83
CHƯƠNG 6 ĐỘ PHỨC TẠP TÍNH TOÁN 93
I. ĐỘ PHỨC TẠP VỀ THỜI GIAN VÀ VỀ BỘ NHỚ 84
II. CÁC LỚP CỦA ĐỘ PHỨC TẠP 84
II.1. Hiện tượng nén 84
II.2. Các họ P, NP và P
−
bộ nhớ (P
−
space) 84
III. RÚT GỌN ĐA THỨC VÀ CÁC BÀI TOÁN NP−ĐẦY ĐỦ 84
III.1. Khái niệm 84
III.2. Các bài toán cổ điển 84
III.3. Ví dụ về rút gọn kiểu đa thức 84
mặt trong câu. Câu rỗng (empty word), được ký hi
ệu là e (ω hoặc e, hoặc l), là
câu có độ dài không, tức không chứa ký tự nào.
Ghép (concatenation) của hai câu là đặt kế tiếp hai câu đã cho (trên cùng
dòng) để nhận được một câu mới. Bằng cách ghép liên tục như vậy cho mọi ký
tự, mọi câu của S, ta nhận được một tập hợp chứa mọi câu có thể trên S, ký hiệu
S
*
. Người ta nói S
*
là một cấu trúc đồng đẳng (nonoide), mà phần tử trung hòa
(neutral element) chính là câu rỗng.
Cho trước một bảng chữ S, người ta định nghĩa một quan hệ có thứ tự toàn
phần (total order) trên S
*
như sau : cho một thứ tự tùy ý trên các ký tự của S,
2 Lý thuyết tính toán
người ta sắp xếp các câu theo một thứ tự phân cấp (hierechical order), đầu tiên là
theo độ dài câu, sau đó theo thứ tự từ vựng (lexicography), hay thứ tự ABC.
Ví dụ :
Cho S = {a, b, c}, với giả thiết thứ tự phân cấp của các ký tự là a < b < c, ta
có thể đánh số các câu của S
*
(kể cả câu rỗng e) bắt đầu từ 1 trở đi như sau :

Hình 1.1. Thứ tự phân cấp trong S
*

II. Các máy (machines)
II.1. Khía cạnh chức năng (functional look)

ac
7
ba
8
bb
9
bc
10
ca
11
cb
12
cc
13

aaa
14
aab
15
aac
16
. . .
Dữ liệu vào
Máy
Dữ liệu ra
Nhập môn lý thuyết tính toán 3

Các tập hợp này tạo thành các ngôn ngữ (language). Hai tập hợp đầu là bù
nhau nếu với mọi dữ liệu vào, máy đều cho một kết quả. Người ta gọi đó là
máy đoán nhận (recognition machine) câu.

tạo thành một ngôn ngữ. Người ta gọi ngôn ngữ này là liệt kê được
(enumerated) bởi máy.
II.2. Khía cạnh cấu trúc (structural look)
Ở đây, ta chỉ quan tâm đến các máy được mô tả đầy đủ về chức năng hoạt
động của chúng. Những máy này có thê :
 Thực hiện các phép toán sơ cấp (elementary operation) trong một khoảng
thời gian hữu hạn. Mỗi phép toán, giả thiết không chia cắt nhỏ hơn được,
được chọn trong một tập hợp hữu hạn các phép toán là một phần mô tả cấu
trúc máy.
 Lần lượt thực hiện các phép toán sơ cấp theo một thứ tự xác định trước, tạo
thành một chương trình (program), là một phần mô tả cấu trúc máy.
Một dãy các phép toán sơ cấp được máy thực hiện liên tiếp được gọi là một
tính toán (computation) của máy.
4 Lý thuyết tính toán
III. Mô hình tính toán
Thay vì phải thay đổi lại máy tính mỗi lần thay đổi bài toán cần giải, người ta
định nghĩa các lớp máy có cùng nguyên lý hoạt động và chúng chỉ khác nhau ở
chương trình.
Người ta gọi mô hình tính toán (model), ký hiệu
T, là sự mô tả tất cả các phép
toán sơ cấp có thể được thực hiện trên những đối tượng nào, cách tác động lên
mỗi một trong chúng như thế nào, và mô tả cách thức chương trình được thực
hiện (execution) trên máy.
Một trường hợp riêng (instance) của mô hình là một máy biệt lập nào đó, gọi
tắt là máy, hoạt động theo cách mô hình tính toán đã chỉ ra. Máy này được định
nghĩa bởi dữ liệu vào của chương trình :
Mô hình + Chương trình = Máy
Một khi một mô hình tính toán
T được định nghĩa, được gọi là một T−máy,
vấn đề đặt ra là làm sao để có thể biết :

− mọi ngôn ngữ
T
2
-liệt kê được cũng là T
1
-liệt kê được.
Hai mô hình được gọi là tương đương (equivalent) nếu mỗi mô hình mạnh
hơn mô hình kia và ngược lại.
Hai mô hình là không thể so sánh với nhau được nếu không tồn tại mô hình
nào ít ra đủ mạnh hơn mô hình kia.

Nhập môn lý thuyết tính toán 5

IV. Định nghĩa bài toán
Trong Tin học lý thuyết, định nghĩa về bài toán (problem) có vai trò đặc biệt
quan trọng, khác với khái niệm thông thường về bài toán được dùng trong lĩnh
vực Toán học hoặc hiểu theo nghĩa thông dụng.
Định nghĩa 1.2 :
Một bài toán là :
− Sự mô tả cách biểu diễn (hữu hạn) các phần tử của một tập hợp hữu hạn
hay vô hạn đếm được.
− Một phát biểu liên quan đến các phần tử của tập hợp này, có thể là đúng,
hoặc có thể là sai tùy theo phần tử được chọn.
Sau đây là một số ví dụ :
Bài toán 1 :
Dữ liệu: Một số nguyên viết trong hệ 10.
Câu hỏi : Số nguyên đã cho có là số nguyên tố hay không ?
Bài toán 2 :
Dữ liệu : Một số nguyên viết trong hệ 10.
Câu hỏi : Có phải số nguyên này được viết dưới dạng tổng của 4 số bình phương

2
) , (u
k
, v
k
).
Câu hỏi : Tồn tại hay không một dãy chỉ số i
1
, i
2
, i
n
sao cho thoả mãn
u
i
1
u
i
2
u
i
n
= v
i
1
v
i
2
v
i

Một máy giải (solve) một bài toán P nếu và chỉ nếu với mọi câu f biểu diễn
một phần tử của tập hợp liên quan đến bài toán này, máy cho phép xác định,
trong một khoảng thời gian hữu hạn, nếu câu này thuộc về L
P
hay L
C
P
.
Người ta phân lớp các bài toán tùy theo độ khó (difficulty) để đưa ra câu trả
lời từ dữ liệu vào đã cho.
Một bài toán là tầm thường (trivial) nếu L
P
= ∅ hoặc nếu L
C
P

= ∅.
Thật vậy, trong trường hợp này, không cần thiết biết dữ liệu đưa vào để đưa ra
câu trả lời. Chú ý rằng, những gì là tầm thường, đó là việc đưa ra câu trả lời,
nhưng có thể rất khó để chứng minh rằng bài toán là tầm thường theo nghĩa này.
Ví dụ, bài toán 2 là tầm thường.
Các bài toán 1 và 3 có cùng câu hỏi, nhưng bài toán 3 giải quyết rất dễ dàng :
chỉ cần đọc qua dữ liệu vào, ng
ười ta có thể đưa ra kết quả, tuy nhiên trong bài
toán 1 thì cần phải xử lý dữ liệu vào. Bài toán 4 phức tạp hơn : người ta chưa biết
phương pháp nào hoạt động một cách đơn định (deterministic) tiêu tốn một lượng
thời gian đa thức (polynomial times) để giải quyết vấn đề đặt ra.
Đối với bài toán 5 thì tính phức tạp còn lớn hơn nữa : người ta biết rằng mọi
phương pháp đều hoạ
t động theo thời gian tối thiểu là lũy thừa. Cuối cùng bài

câu. Thể hiện các song ánh (bijection) giữa N và mỗi một tập hợp vừa nêu.
4) Cho S là một bảng chữ kích thước (bản số) n. Với mọi câu w∈S
*
, ký hiệu |w|
là độ dài của w và m(w) là số thứ tự của w trong thứ tự phân cấp đã cho. Hãy
tìm cách tính m(w) khi biết w.
5) Chứng minh rằng N
N
không phải là vô hạn đếm được. Tập hợp các chương
trình Pascal có phải là vô hạn đếm được hay không ? Tập hợp các hàm f: N →
N tính được nhờ một chương trình Psacal có là vô hạn đếm được hay không ?
Từ đó suy ra rằng tồn tại các hàm từ N vào N không là vô hạn đếm được nhờ
một chương trình Pascal.
6) Viết một chương trình để liệt kê :
− các cặp số nguyên
− các dãy h
ữu hạn các số nguyên
− các câu trên một bảng chữ hữu hạn (chẳng hạn S={a, b, c})
− các cặp câu
− các dãy hữu hạn các câu.



PGS.TS. PHAN HUY KHÁNH biên soạn 9

CHƯƠNG 2
Mô hình các máy RAM
« I like the dreams of the future better than
the history of the past »
Jefferson

 Một tập hợp các đơn vị nhớ được đánh số chứa chương trình của máy RAM
dưới dạng một dãy các lệnh sơ cấp (primary instructions) không bị thay đổi
trong quá trình chạy (thực hiện). Mỗi lệnh được lưu trữ trong một đơn vị
nhớ, được đánh số tương ứng với số thứ tự hay nhãn của lệnh (label).
 Một đơn vị nhớ chứa số thứ tự của lệnh đang được thực hiện, được gọi là
thanh đếm lệnh (OC − Ordinal Counter). Lúc đầu nội dung là của OC là 1.
Trong kiểu máy này, người ta truy cập trực tiếp đến mỗi thanh ghi bởi địa chỉ
của thanh ghi đó. Chính lý do này mà kiểu máy này được đặt tên là Random
Access Memory (viết tắt RAM).
10 Lý thuyết tính toán
Hình 2.1 Sơ đồ một máy RAM
Mỗi chương trình của máy RAM gồm một dãy lệnh sơ cấp, mỗi lệnh được tạo
thành từ 2 thành phần : mã lệnh (operation code) và toán hạng (operand) :
Mã lệnh
T
oán hạng
Các lệnh được phân thành nhóm theo chức năng của phần mã lệnh như sau :
Nhóm lệnh gán :
LOAD Operand
STORE Operand
Nhóm lệnh số học :
INCR Operand
DECR Operand
AD Operand
SUB Operand
MULT Operand
DIV Operand
Nhóm lệnh nhảy (hay lệnh ngắt, cũng còn gọi là lệnh chuyển điều khiển) :
JUMP Label
JGTZ Label

3 . . . Băng ra

Chương trình
x
1
x
2
. . . x
n Băng vào

Mô hình các máy RAM 11

Theo nguyên tắc địa chỉ, phần toán hạng là địa chỉ (address) của toán hạng
tham gia phép toán chỉ định bởi phần mã lệnh. Toán hạng có thể là một trong ba
kiểu sau :
Kiểu địa chỉ Ý nghĩa
Số nguyên n Chỉ nội dung của thanh ghi thứ n (R
n
).
A: n (A = Absolute) toán hạng chính là số nguyên n đó.
I: n (I = Indirection) toán hạng là nội dung của thanh ghi có số thứ
tự là nội dung của thanh ghi R
n
. Đây là kiểu lệnh gián tiếp.
Nếu lệnh là một lệnh nhảy thì địa chỉ chính là số thứ tự của lệnh trong chương
trình. Các lệnh trên đây của máy RAM điển hình cho các lệnh của ngôn ngữ
assembler. Tuy nhiên ở đây vắng mặt các lệnh xử lý ký tự và các lệnh logic nhằm
đơn giản cách trình bày.
Thứ tự thực hiện các lệnh của chương trình là tuần tự (on sequence), bắt đầu
t

LOAD A: n ACC ← giá trị n
LOAD I: n ACC ← <<n>>
STORE n n ← <ACC>
STORE I: n <n> ← <ACC>
INCR n n ← <n> + 1
DECR n n ← <n> - 1
ADD n ACC ← <ACC> + <n>
SUB n ACC ← <ACC> − <n>
MULT n ACC ← <ACC> × <n>
DIV n ACC ← <ACC> / <n>
JUMP n CO ← n
JGTZ n CO ← n nếu <ACC> ≥ 0
JZERO n CO ← n nếu <ACC> = 0
Cả hai trường hợp trên, nếu không thỏa mãn, CO ← <CO> + 1
HALT Dừng máy
READ n n ← số nguyên trong ô dưới đầu đọc của băng,
đầu đọc dịch một ô qua phải
WRITE n Nội dung <n> được ghi vào ô dưới đầu ghi,
đầu ghi dịch qua phải một ô.
Ví dụ 2.1 : Chương trình RAM sau đây đánh giá trị n!
READ 0 đọc một giá nguyên n vào ACC
JZERO 10 nếu n = 0, nhảy đến nhãn 10,
nếu không, thực hiện lệnh tiếp theo
STORE 1 R
1
← <ACC>
4: STORE 2 R
2
← <ACC>
DECR 1 R

LOAD 1 ACC ← <R
1
>
JGTZ 6 nếu <ACC> ≥ 0, nhảy đều 6
WRITE A:0 in ra 0
JUMP 22 về lệnh dừng
6 : LOAD 1 ACC ← <R
1
>
STORE 2 R
2
← <ACC>
LOAD 1 ACC ← <R
1
>
DECR 0 ACC ← <ACC> − 1
STORE 3 R
3
← <ACC>
11 : LOAD 3 ACC ← <R
3
>
JGTZ 14 nếu <ACC> ≥ 0, nhảy đến 14
JUMP 21 nhảy đến 21 nếu <ACC> < 0
14: LOAD 2 ACC ← <R
2
>
MULT 1 ACC ← <ACC>
*
<R

dừng.
Ta có thể giải thích ánh xạ này ở dưới hai dạng : dạng hàm và dạng ngôn ngữ.
14 Lý thuyết tính toán
Dạng hàm f : S* → S*
Giả sử chương trình P luôn đọc được từ băng vào n số nguyên x
1
, x
2
, , x
n
và
ghi lên băng ra không quá một số nguyên y ở ô đầu tiên, khi đó ta nói P tính hàm
f (x
1
, x
2
, , x
n
) = y.
Dạng ngôn ngữ L
⊆
S*
Giả sử trên băng vào có câu w = a
1
a
2
a
n
với a
i

thập phân, hoặc biểu diễn nhị phân. Cách biểu diễn nhị phân có lợi thế hơn vì chỉ
sử dụng hai chữ số. Máy tính sẽ chuyển đổi chuỗi ký tự biể
u diễn số nguyên
thành biểu diễn nhị phân để đặt trong các thanh ghi, sau đó chuyển đổi kết quả
đang ở dạng biểu diễn nhị phân của số nguyên thành chuỗi ký tự trên băng ra.
Điểm 1) trên đây có nghĩa : trong mọi trường hợp, kích thước của bài toán cần
giải là đủ bé để bộ nhớ máy tính có thể chứa hết ở dạng nhị phân trong các đơn vị
nhớ, hay từ nh
ớ (memory word). Chú ý rằng nếu chỉ làm việc với cách biểu diễn
số nguyên bởi chuỗi các chữ số thì không còn giả thiết số lớn tùy ý nữa.
Mô hình các máy RAM 15

Cuối cùng, sự khác nhau ở điếm (2) đưa đến việc xây dựng một mô hình
tương tự mô hình RAM, nhưng chương trình được đặt trong các thanh ghi (và do
vậy có thể bị thay đổi), được gọi là mô hình các máy RASP (Random Access
with Stored Program). Sự khác nhau cơ bản với các máy RAM là vùng nhớ lưu
giữ chương trình của RASP hoàn toàn không khác gì so với các vùng nhớ khác.
Máy RASP
Để thuận tiện cách trình bày, ta quy ước rằng mỗi lệnh RASP chiếm chỗ hai
thanh ghi liên tiếp nhau : thanh ghi đầu chứa trườ
ng toán hạng, thanh ghi thứ hai
chứa trường địa chỉ của lệnh.
Hình 2.2 Sơ đồ một máy RASP

Trong máy RASP, thanh tổng luôn luôn là R
0
, thanh ghi R
1
dùng để lưu giữ
trung gian nội dung của thanh tổng.

x
1
x
2
. . . x
n Băng vào

16 Lý thuyết tính toán
II. Mô phỏng một máy bởi một máy khác
Từ đây trở đi, người ta thường phải mô phỏng một máy bởi một máy khác :
máy mô phỏng sẽ bắt chước hay nhại lại (mime) mỗi một lệnh của máy được mô
phỏng, bằng cách thực hiện nhiều lệnh (nói chung) để đi đến cùng một kết quả.
Khi có một máy RAM M có chương trình P chạy và sử dụng đến thanh ghi 0
và các thanh ghi từ 1 đến p (giá trị của p thay
đổi tùy theo dữ liệu), người ta nói
rằng một máy RAM M’ có chương trình P’ mô phỏng chức năng của máy RAM
M nếu :
 Tồn tại một ánh xạ I từ N vào N mà biến 0 thành 0.
 Mỗi lệnh của P được thay thế bởi một lệnh của P’ sao cho, mỗi lần thực
hiện chương trình P (nghĩa là với mọi dữ liệu), nội dung mỗi thanh ghi I (r)
của M’ sau khi thực hiện dãy các lệnh của P’ là giống như nội dung của
thanh ghi R của M sau khi thực hiện các lệnh tương ứng của P.
Ví dụ 2.3 : Dịch chuyể
n các địa chỉ thanh ghi.
Xuất phát từ một máy RAM có chương trình P khi chạy sử dụng thanh ghi 0
và các thanh ghi từ 1 đến p, ta có thể xây dựng một máy RAM khác có chương
trình P
k
mô phỏng trình P với ánh xạ I xác định bởi :
I (0) = 0

ghi số
50 đến 61, với giả thiết chương trình có trên hai lệnh kiểu gián tiếp. Lệnh
đầu tiên của nhóm 6 lệnh này là lưu giữ nội dung của thanh tổng vào thanh ghi
R
1
:
50 STORE
51 1 R
1
← <ACC>
Lệnh thứ hai nạp vào thanh tổng nội dung của thanh ghi n + p’ − p (tương ứng
với thanh ghi n trong chương trình xuất phát) :
52 LOAD
53 n + p’- p ACC ← <R
n
> + (p’ − p)
Lệnh thứ ba tăng nội dung của thanh tổng lên p’ − p để lúc này thanh tổng
chứa địa chỉ của thanh ghi chứa giá trị cần nhân :
54 ADD A:
55 p’- p ACC ← <ACC> + (p’ − p)
Lệnh thứ tư gán trực tiếp lệnh thứ sáu bằng cách thay đổi trường địa chỉ của
lệnh này (việc thực hiện chương trình làm thay đổi bả
n thân chương trình đó) :
56 STORE
57 61 R
61
← <ACC>
Lệnh thứ năm khôi phục nội dung lúc đầu của thanh tổng :
58 LOAD
59 1 ACC ← <R


2 READ READ

3 27
R
27
← a
37

4 READ READ

5 28
R
27
← b
38

6 LOAD A: LOAD A:

7 27
ACC ← <R
27
>
37

8 STORE STORE

9 26
R
26

← < R
26
> + 1
36

18 LOAD A: LOAD A:

19 1
ACC ← 1
1
Phần này là
dịch chuyển của P
với ánh xạ :
I(r) = r+p’-p = r+10

20
ADD I: STORE

21
26
ACC ← <ACC> + <<R
26
>>
1
R
1
← <ACC>

22 WRITE
LOAD


1
ACC ← <R
1
>

30

ADD

31

Nội dung thay đổi : số x
→
0
ACC←<ACC> +
<R
x
>

32

WRITE 33

0
Cách biểu diễn thứ hai là sử dụng một dãy chữ số trên bảng chữ {0 9}. Thực
tế, ngay cả khi người ta có thể biểu diễn trong một thanh ghi nhiều ký tự (thường
không quá 4), thì để biểu diễn một số nguyên cũng đòi hỏi có nhiều thanh ghi.
Mặc dù dải số nguyên có thể biểu diễn
được là khá lớn, nhưng do số lượng các
thanh ghi trong máy tính hiện nay bị hạn chế nên cách biểu diễn này cũng chưa
phải tối ưu.
III.1. Mô phỏng các phép toán trên chuỗi ký tự bởi các
phép toán trên các số nguyên
Mỗi ký tự được mã hóa bởi một dãy các chữ số nhị phân {0, 1} (chẳng hạn 8
chữ số cho một ký tự). Một chuỗi bit như vậy có thể dùng để biểu diễn các số
nguyên nhờ thực hiện các phép toán trên các số nguyên.
Chẳng hạn, ghép 198 và 7, dẫn đến phép nhân số nguyên biểu diễn chuỗi 198
với 2
8
rồi cộng thêm số nguyên biểu diễn chuỗi 7 vào tích số nhận được :
Hình 2.4 Ghép hai số nguyên
Ngược lại, các phép toán số học có thể được thực hiện trên biểu diễn các số
nguyên bởi các chuỗi ký tự, đó là các phép tính sơ cấp.
Chú ý rằng khi người ta tiến hành các phép toán trên các số nguyên theo cách
biểu diễn nhị phân, người ta đã xử lý trên các câu của bảng chữ {0, 1}, và phép
toán được thực thi trên các ký tự.

198 7
198
2
8

7
~ × +