Download May Turing PDF

TitleMay Turing
File Size504.2 KB
Total Pages29
Document Text Contents
Page 1

MỤC LỤC

CHƯƠNG 1. MÁY TURING VÀ THUẬT TOÁN................................................1

1. Mô tả và định nghĩa về máy Turing..............................................................1

1.1. Mô tả phi hình thức về máy turing .....................................................................1
1.2. Định nghĩa hình thức của máy Turing (máy Turing đơn băng – Single tape
Turing machine) ........................................................................................................3
1.4. Ví dụ về máy Turing...........................................................................................4
1.5. Sơ đồ chuyển vị cho máy Turing .......................................................................5

2. Giới thiệu về máy Turing phổ dụng .............................................................6

3. Máy turing với biểu diễn thuật toán...........................................................10

3.1. Khái niệm thuật toán .......................................................................................10
3.2. Biểu diễn thuật toán một cách hình thức bằng máy Turing..............................11

CHƯƠNG 2. TÍNH KHẢ QUYẾT CỦA THUẬT TOÁN............................16

1. Tổng quan về tính khả quyết của thuật toán..............................................16

2. Luận đề Church-Turing..............................................................................17

3. Các chương trình như các bộ nhận dạng ngôn ngữ...................................18

3.1. Các chương trình và máy Turing.....................................................................20
3.2. Các hàm tính toán..............................................................................................20

4. Máy Turing và vấn đề khả quyết................................................................22

4.1. Các tập đệ quy kể được và khả quyết................................................................22
4.1.1. Một số định nghĩa...........................................................................................22
4.1.2. So sánh RE và tính khả quyết.........................................................................22
4.1.3. Tính kể được...................................................................................................23
4.2. Các ngôn ngữ đệ quy liệt kê .............................................................................24
4.2.1. Ngôn ngữ đệ quy............................................................................................24
4.2.2. Ngôn ngữ đệ quy liệt kê ................................................................................24
4.3. Các bài toán khả quyết .....................................................................................24

5. Một số vấn đề máy Turing không giải được...............................................26

5.1. Bài toán in (printing problem) và bài toán dừng(halting problem)...................26
5.2. Hàm dừng..........................................................................................................26
5.3. Entscheidungsproblem......................................................................................26

TÀI LIỆU THAM KHẢO...............................................................................28

...........................................................................................................................28

Page 2

1Máy Turing và tính khả quyết của thuật toán

CHƯƠNG 1. MÁY TURING VÀ THUẬT TOÁN

1. Mô tả và định nghĩa về máy Turing

1.1. Mô tả phi hình thức về máy turing

Khái niệm của máy Turing dựa trên ý tưởng của một người đã thực hiện một
thủ tục rất rõ ràng bằng cách thay đổi những nội dụng của một băng giấy vô hạn, mà
nó được phân thành các ô vuông có thể chứa một trong các tập hữu hạn các ký hiệu.
Người này cần nhớ một trong các tập trạng thái hữu hạn và một thủ tục được trình
bày trong nhiều bước cơ bản dưới dạng “Nếu trạng thái của bạn là 42 và ký hiệu mà
bạn thấy là ‘0’ thì thay thế nó bằng ‘1’, di chuyển một ký hiệu sang phải, và thừa
nhận rằng trạng thái 17 như một trạng thái mới của bạn”.

Trong một số mô hình, đầu đọc (head) di chuyển dọc theo băng tĩnh
(Stationary tape). Chỉ thị để được thực hiện (q1) được chỉ ra bên trong đầu đọc.
Trong mô hình này, băng trống là tất cả các ô bằng 0. Các ô vuông được tô đậm,
gồm ô đã được quét qua bởi đầu đọc, và các ô vuông được đánh dấu 1, 1, B và biểu
tượng đầu đọc, tạo thành trạng thái của hệ thống.

Một cách rõ ràng hơn, có thể hình dung một máy Turing sẽ bao gồm các
thành phần sau:

• Một băng (TAPE), hay còn gọi là một bộ nhớ vô hạn, dưới dạng một
băng gồm nhiều ô, có thể kéo dài vô hạn về phía phải. Mỗi ô trên băng có
thể chứa một ký hiệu thuộc một bộ chữ, gọi là bộ chữ trên băng (mà một
phần trong đó là bộ chữ vào, dùng cho xâu vào);

• Một đầu đọc (HEAD) di chuyển ở trên băng, ở mỗi thời điểm nhìn
vào một ô trên băng;

• Một tập hữu hạn các trạng thái, trong đó có phân biệt một trạng thái
đầu và một tập hợp các trạng thái đã được thừa nhận;

• Một hàm dịch chuyển chứa một tập hữu hạn chỉ thị cho phép cứ với
mỗi trạng thái của máy và một ký hiệu đọc được trong ô đối diện với đầu
đọc, máy sẽ thực hiện các bước như sau:

o Chuyển trạng thái

o In một ký hiệu trên băng tại ô đang duyệt (nghĩa là
thay ký hiệu đọc được trên băng bằng ký hiệu nào đó)

Page 14

13Máy Turing và tính khả quyết của thuật toán

được cn-1.2+sn-1. Bit đứng đầu của tổng là sn=cn-1. Kết quả, thủ tục này tạo ra được
khai triển nhị phân của tổng, cụ thể là a+b = (sn sn-1 sn-2 ... s1 s0)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 đó qf là một trạng thái kết thúc)

q0w(x)€w(y) M qf w(x + y)€,

Q = {q0, q1, q2, q3,…., q9, qf}, F = {qf}

Với bảng trạng thái được cho bởi đồ thị trạng thái như sau:

• Sau khi tính toán, w(x + y) sẽ ở trên băng và được theo sau bởi một kí
tự €, và đầu đọc sẽ được đặt trên kí tự phải cùng của kết quả.

Như trên, chúng ta đã thấy máy Turing có thể thực hiện được các phép toán
cơ bản và quan trọng những cái mà có trong tất cả các máy tính. Vì trong các máy
tính số, các phép toán cơ bản như vậy là các thành phần cơ bản cho các lệnh phức
tạp hơn, sau đây là một ví dụ trình bày khả năng máy Turing kết hợp các phép toán
này lại với nhau.

Giả sử chúng ta thiết kế máy Turing tính toán hàm sau:

Page 15

14Máy Turing và tính khả quyết của thuật toán

Ta xây dựng mô hình tính toán như sau:

Vấn đề xây dựng được hàm tính toán được yêu cầu của chúng ta bây giờ sẽ
được chuyển thành xây dựng các bộ so sánh, bộ cộng và bộ xóa. Điều này cũng có
nghĩa rằng bài toán phức tạp của chúng ta đã được chuyển thành kết hợp các phép
toán cơ bản.

Với khá nhiều bằng chứng mạnh mẽ tuy chưa đủ là một chứng minh chặt
chẽ, nhưng chúng ta chấp nhận miêu tả chính xác của ý tưởng tổng quát về thuật
toán trong một bộ chữ cái được thực hiện bởi máy Turing là hoàn toàn đầy đủ. Có
nghĩa rằng, đối với mọi thuật toán trong bảng chữ cái cụ thể, có thể xây dựng một
thuật toán Turing cho cùng các kết quả với cùng dữ liệu ban đầu như thuật toán .
Sự chấp nhận này được gọi là luận đề Turing trong lý thuyết thuật toán, như một
định nghĩa của một “sự tính toán cơ học”. Cụ thể,

• Bất kỳ cái gì có thể được thực hiện trên bất kỳ máy tính số đang tồn
tại nào đều có thể được thực hiện bởi một máy Turing.

• Không ai có thể đưa ra một bài toán, có thể giải quyết được bằng
những gì mà một cách trực quan chúng ta xem là một thuật toán, mà đối
với nó không tồn tại máy Turing nào giải quyết được.

• 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.

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à:

q0w M qf f(w), qf ∈F, ∀w ∈ D.

Luận đề Turing ngay lập tức được chấp nhận rộng rãi. Thông qua việc thực
hiện các phép tính dựa trên một kế hoạch được chọn trước, các nhà khoa học đã tiến
hành theo một cách tương đương với máy Turing: xem xét một số vị trí trong bài
viết của mình và ở trong một “trạng thái trí tuệ”nhất định, họ tiến hành sửa đổi

Page 29

28Máy Turing và tính khả quyết của thuật toán

TÀI LIỆU THAM KHẢO

1. Dan Dougherty. Notes on Decidability. Worcester Polytechnic Institute, 2007.

2. Jack Copeland. Computation.
www.blackwellpublishing.com/pci/downloads/SampleChapter.pdf

3. Jack Copeland. The Church-Turing Thesis. Stanford Encyclopedia of Philosophy,
2002.

4. Lê Mạnh Thạnh. Nhập môn Ngôn ngữ hình thức và Ôtômat hữu hạn. NXB Giáo
dục, Đà Nẵng, 1998.

5. Nguyễn Gia Định. Giáo trình Lý thuyết Ngôn ngữ hình thức và Ôtômat. Huế, 2004.

6. Nguyễn Văn Ba. Lý thuyết Ngôn ngữ và Tính toán. NXB Đại học Quốc gia Hà Nội,
Hà Nội, 2006.

7. Peter Gács and László Lovász. Algorithmic decidability. Lecture Notes, Yale
University, 1999.

8. Wikipedia, http://en.wikipedia.org/wiki/Wiki

http://en.wikipedia.org/wiki/Wiki
http://www.blackwellpublishing.com/pci/downloads/SampleChapter.pdf

Similer Documents