Tiểu luận môn Lý Thuyết Tính Toán Nhóm 1
I H C À N NGĐẠ Ọ Đ Ẵ
TR NG I H C BÁCH KHOAƯỜ ĐẠ Ọ
KHOA CÔNG NGH THÔNG TINỆ

tàiĐề :
NH NG V N MÀ MÁY TÍNH KHÔNGỮ Ấ ĐỀ
TH GI I QUY T CỂ Ả Ế ĐƯỢ
GVHD : PGS. TS. Phan Huy Khánh
HVTH : VÕ MINH TI NẾ
H NG C TÚỒ Ọ
TR N VI TẦ Ế
L PỚ : Khoa h c máy tính k24ọ
1/15
à N ng, tháng 05/2012Đ ẵ
Tiểu luận môn Lý Thuyết Tính Toán Nhóm 1
LỜI MỞ ĐẦU
Liệu có thể chế tạo ra một loại máy tính nào đó có hiểu được con người và
thông minh như người hay không? Với thế hệ máy tính ngày nay có thể hiểu được như
bộ não của người không? Tìm hiểu chính bản thân mình – đó là niềm khát khao của
loài người trong suốt quá trình phát triển. Những thành tựu khoa học vang dội gần
đây như nhân bản vô tính, giải mã bộ gen người,… phần nào tạo nên ấn tượng con
người sắp đạt đến chỗ hiểu được chính mình. Như vậy, con người đang đứng trước
một câu hỏi lớn: liệu có thể chế tạo ra các máy tính thông minh được không? tức là sẽ
có hay không các máy tính biết tư duy như con người?
Công trình của A. Turing (1912-1954), nhà toán học người Anh, cũng nằm
trong hướng nghiên cứu vấn đề hình thức hoá toán học (theo tinh thần bài toán mà
Hilbert đặt ra năm 1928 tại Hội nghị Toán học thế giới). Turing chứng minh rằng,
mọi quá trình tính toán tổng quát có thể thực hiện được bởi một “máy”. Máy này gồm
có một cuộn băng độ dài vô hạn với các ô vuông, một thiết bị có hữu hạn trạng thái

Chương I và Chương II được thực hiện trên nền tảng lý thuyết của cuốn sách
"Introduction to languages and theory of computation" của John C. Martin và
tham khảo theo lý thuyết của tài liệu "Lý thuyết tính toán" của PGS. TS. Phan Huy
Khánh. Học viên Võ Minh Tiến, Hồ Ngọc Tú chịu trách nhiệm phần dịch Anh-Việt.
Phần ví dụ minh họa và các chứng minh liên quan do cả 3 học viên Trần Viết, Hồ
Ngọc Tú và Võ Minh Tiến phối hợp thực hiện. Phần bài tập do học viên Hồ Ngọc Tú
thực hiện, học viên Trần Viết chịu trách nhiệm kiểm tra, chỉnh sửa lỗi và thiết kế bản
in. Nhóm thực hiện xin chân thành cảm ơn các tác giả đã cho phép nhóm tham khảo tài
liệu.
4/15
Tiểu luận môn Lý Thuyết Tính Toán Nhóm 1
MỤC LỤC
LỜI MỞ ĐẦU 2
NHỮNG BÀI TOÁN KHÔNG THỂ GIẢI ĐƯỢC 6
I. CÁC VẤN ĐỀ KHÔNG THỂ GIẢI ĐƯỢC TRÊN MÁY TÍNH 6
II. CÁC CHƯƠNG TRÌNH IN “Hello, World” 7
III. GIẢ THIẾT VỀ CHƯƠNG TRÌNH KIỂM TRA “HELLO, WORLD” 9
5/15
Tiểu luận môn Lý Thuyết Tính Toán Nhóm 1
CHƯƠNG I
NHỮNG BÀI TOÁN KHÔNG THỂ GIẢI ĐƯỢC
Khi đề cập đến máy Turing, ta thường quan tâm đến các lớp ngôn ngữ đơn giản
và những cách đơn giản được sử dụng trong giải quyết các vấn đề như: phân tích giao
thức, tìm kiếm văn bản hoặc các chương trình phân tích văn phạm… Trong phần trình
bày này, nhóm em sẽ trình bày vấn đề “những ngôn ngữ nào sẽ không thể giải bằng
thiết bị tính toán”, vấn đề này tương đương với câu hỏi “máy tính có thể làm được
những gì?”, việc nhận dạng văn bản trong 1 ngôn ngữ là cách diễn đạt vấn đề này một
cách tốt nhất.
Ta bắt đầu với một vấn đề sau, bằng cách sử dụng ngôn ngữ lập trình C, để chỉ
ra rằng có một số vấn đề máy tính không thể giải được – đó là những vấn đề được gọi

y, z) theo một trật tự xác định và các số phải là số nguyên dương.
Để tổ chức tìm kiếm một các hợp lý, ta sử dụng biến thứ tư là total, giá trị bắt đầu của
total là 3 và trong vòng lặp while nó sẽ được tăng một đơn vị mỗi lần. Bên trong vòng
lặp chúng ta phân chia total cho 3 biến x, y, z . Đầu tiên cho x chạy từ 1 cho đến total –
2, y sẽ chạy từ total – 1 – x còn lại z sẽ chạy từ total – x – y. Nếu trong vòng lặp bộ ba
(x, y, z) được kiểm tra thỏa điều kiện x
n
+y
n
=z
n
thì sẽ in ra màn hình hello world, còn
nếu không thì sẽ không hiển thị gì.
int exp(int i, n)
/* computes i to the power n *
{
int ans, j;
ans = 1;
for(j=1; j<=n; j++)
7/15
Tiểu luận môn Lý Thuyết Tính Toán Nhóm 1
ans *=i;
return(ans);
}
main()
{
int n, total, x, y, z;
scanf(“%d”, &n);
total = 3;
while(1){

in kết quả gồm 3 kí tự “Yes” hoặc in 2 kí tự là “No”.
Nếu vấn đề có một thuật toán giống như H, mà luôn luôn thể hiện một cách
chính xác xem một thể hiện của vấn đề đã trả lời "có" hoặc "không”, sau đó vấn đề
được gọi là không giải quyết được.
Hình 8.3. Giả thuyết H là một chương trình kiểm tra chương trình in “hello, world”
Để chứng minh sự mâu thuẫn, chúng ta sẽ thay đổi một số H, sau đó xây dựng
một chương trình liên quan được gọi là H2 mà chúng tôi cho thấy không tồn tại.Kể
từ khi thay đổi để H chuyển đổi đơn giản có thể được thực hiện vào bất kỳ chương
trình C nào, khẳng định đã có sự tồn tại của H, do đó, giả định chúng ta đặt ra
đã mâu thuẫn.
Để đơn giản hóa cuộc thảo luận, chúng ta sẽ làm một chương trình giả định bằng
ngôn ngữ C . Chương trình này sẽ làm cho công việc của dễ dàng hơn, không khó
khăn hơn, vì vậy nếu chúng ta có thể hiển thị một "hello-thế giới thử nghiệm" cho các
chương trình hạn chế không tồn tại, thì chắc chắn không có thử nghiệm như vậy có
thể làm việccho một lớp học rộng lớn hơn của chương trình. Giả định của chúng tôi là:
9/15
I
Hello -world
Tester
H
H1
yes
hello, world
P
Tiểu luận môn Lý Thuyết Tính Toán Nhóm 1
1. Đầu ra tất cả là dựa trên ký tự, ví dụ như, chúng tôi không sử dụng một gói
phần mềm đồ họa hay cơ sở nào khác để làm cho sản lượng đó không phải
là trong các hình thức của các nhân vật.
2. Tất cả các đầu ra dựa trên ký tự được thực hiện bằng cách sử dụng printf, chứ
không phải là char ( ) hoặc một chức năng đầu ra dựa trên ký tự.

Hình 8.5. H2 giống như H1, nhưng nó chỉ sử dụng P thay vì cả P và I.
Chúng tôi đã sẵn sàng để chứng minh H-2 không thể tồn tại. H1 không tồn
tại,và tương tự như vậy, H không tồn tại.Các đối số là để hình dung những gì
H2 không là chính nó như đầu vào. Tình trạng này được đề xuất trong hình. 8.6. Nhớ
lại rằng H2, cho bất kỳ P chương trình như là đầu vào, làm cho đầu
ra có nếu P in “hello,world” khi đưa ra chính nó như là đầu vào. Ngoài ra,
H2 in “hello, world” nếu P, cho chính nó như là đầu vào, không in “hello, world” như
kết quả đầu tiên của nó.
Hình 8.6. H2 hoạt động thế nào khi xem chính nó là đầu vào.
11/15
H2
yes
hello, world
P
H2
yes
hello, world
H2
Tiểu luận môn Lý Thuyết Tính Toán Nhóm 1
Nó xuất hiện trong hình. 8,6 với đầu ra là “hello, world”, vì nó là một hay
khác.Nhưng nếu H2 xem chính nó như là đầu vào, in “hello, world” đầu
tiên, sau đó đầu ra của nó là thông báo “yes”. Chúng ta có thể tranh luận rằng nó làm
cho đầu ra khác.
Tình trạng này là nghịch lý, và chúng tôi kết luận rằng H2 không thể tồn
tại. Kết quả là, chúng tôi đã mâu thuẫn với giả định rằng H tồn tại.Vậy chúng ta
đã chứng minh rằng không có chương trình H có thể nhận chương
trình P được với đầu vào I để in” hello, world” như kết quả đầu tiên.
IV. Việc giảm một vấn đề đến những vấn đề khác
Bây giờ, chúng ta có một vấn đề đó là liệu có làm chương trình với dữ liệu vào
in ra hello, world như là điều đầu tiên nó in hay không? Điều này chúng ta biết là máy

Một chương trình được gọi là không giải quyết được hay không quyết định được đều
có thể cho ra kết quả khác nhau nhưng với những dữ liệu đầu vào khác nhau. Còn
riêng bài toán này thì cùng một chương trình cùng một dữ liệu đầu vào nếu cho ra kết
quả khác nhau thì chỉ có khi chúng ta sử dụng hàm random. Ví dụ như chương trình
sau có đầu vào là n là số nguyên dương. Chương trình sẽ in ra một số nguyên bất kỳ là
tích của n với random(100).
void main()
{
int n, s;
printf(“nhap so nguyen duong n”);
scanf(“%d”, &n);
s= n* random(100);
printf(s);
}
Chương trình sẽ in ra s, dù có thể cùng một dữ liệu đầu vào nhưng kết quả của s có thể
là khác nhau.
Nếu không sử dụng hàm random thì sẽ không có chương trình nào thảo mãn yêu cầu
bài toán trên.
14/15
Tiểu luận môn Lý Thuyết Tính Toán Nhóm 1
Tài liệu tham khảo
[1] John C. Martin, Introduction to languages and the theory of coputation, The
McGraw-Hill Companies, Inc, 1997.
[2] Phan Huy Khánh, Giáo trình lý thuyết ngôn ngữ hình thức và Ôtômat, Đà
Nẵng, 1998.
[3] TS. Phan Huy Khánh, Lý thuyết tính toán, Đà Nẵng, 1999.
15/15