<< Chapter < Page Chapter >> Page >

Mô phỏng mô hình RAM bởi máy Turing

ĐỊNH LÝ 7.6: Một máy Turing có thể mô phỏng một RAM, với điều kiện là mỗi chỉ thị RAM cũng có thể được mô phỏng bởi một TM.

Chứng minh

Ta sử dụng một TM M nhiều băng để thực hiện quá trình mô phỏng. Một băng của M giữ các từ của RAM được cho bởi các giá trị như dưới đây. Băng có dạng sau :

# 0*v0 # 1*v1 # 10*v2 # …# i*vi # …

trong đó vi là nội dung băng viết dưới dạng nhị phân của từ thứ i. Tại mỗi thời điểm, sẽ có một số hữu hạn các từ của RAM có thể được dùng và M chỉ cần lưu giữ lại các giá trị cho đến khi có một số lượng từ lớn nhất được sử dụng sau đó.

RAM có một số hữu hạn các thanh ghi số học. M dùng một băng để giữ nội dung của mỗi thanh ghi này, một băng để giữ số đếm vị trí (location counter), nơi chứa số thứ tự các từ mà chỉ thị kế tiếp sẽ gọi đến. Và một băng nữa dùng như là thanh ghi địa chỉ bộ nhớ (memory address register) trong đó lưu giữ số của từ nhớ.

Giả sử rằng 10 bit đầu tiên của một chỉ thị biểu thị một toán tử chuẩn của máy tính, chẳng hạn như LOAD, STORE, ADD, … và những bit sau đó xác định địa chỉ của một toán hạng. Trong khi chúng ta sẽ xem xét một cách chi tiết việc cài đặt tất cả các chỉ thị máy tính chuẩn, một ví dụ minh họa sẽ cho thấy điều này rõ ràng hơn. Giả sử băng số đếm vị trí của M giữ số i trong hệ nhị phân. M duyệt băng này đầu tiên từ bên trái và tìm thấy # i*. Nếu một khoảng trống được đếm trước khi tìm thấy # i*, có nghĩa là không có chỉ thị nào trong từ i, vì thế RAM và M ngừng lại. Nếu # i* được tìm thấy, chuỗi bit theo sau ký hiệu * cho đến ký hiệu # sau đó sẽ được xem xét. Giả sử 10 bit đầu tiên là mã lệnh của “ADD to register 2” và phần chuỗi bit còn lại là một số j trong hệ nhị phân. M thêm 1 vào i trên băng số đếm vị trí và sao chép j vào băng địa chỉ bộ nhớ. Sau đó, M lại tìm kiếm # j* trên băng đầu tiên, một lần nữa lại bắt đầu từ bên trái (chú ý rằng # 0* đánh dấu vị trí cận trái). Nếu # j* không tìm thấy, ta giả sử từ j giữ 0 và đi tiếp đến chỉ thị kế tiếp của RAM. Nếu # j* vj# được tìm thấy, vj sẽ đựoc thêm vào nội dung của thanh ghi 2, nơi chứa chính nó trên băng. Tiếp tục lặp lại vòng lặp này với chỉ thị kế tiếp.

Lưu ý rằng trong giải thuật này, mặc dù mô phỏng RAM dùng một máy Turing nhiều băng, nhưng theo Định lý 7.2, nếu ta dùng TM với một băng vô hạn hai chiều cũng sẽ thành công song sẽ phức tạp hơn.

Máy turing như là một bộ liệt kê

Ta đã xét máy Turing như là một máy dùng nhận dạng ngôn ngữ và tính toán các hàm. Một quan điểm rất có ích nữa là xem máy Turing như là bộ liệt kê, tức là nó có khả năng sinh ra ngôn ngữ.

Xét máy Turing có nhiều băng, một trong các băng đó được xem là băng output, trên băng này một ký hiệu được viết lên sẽ không bị thay đổi và đầu đọc của băng này không bao giờ dịch trái.

Giả sử trên băng output, M sẽ viết chuỗi các ký tự thuộc bộ chữ cái , các chuỗi được viết ngăn cách nhau bởi dấu #. Ta định nghĩa G(M) là ngôn ngữ sinh bởi máy Turing M, là tập hợp tất cả các từ w  * được viết giữa hai dấu # trên băng output. Chú ý rằng trừ khi M không dừng, G(M) luôn luôn hữu hạn. Ta cũng không yêu cầu các từ được sinh ra theo một thứ tự nào đó, và cũng không yêu cầu mỗi từ chỉ sinh ra đúng một lần.

Get Jobilize Job Search Mobile App in your pocket Now!

Get it on Google Play Download on the App Store Now




Source:  OpenStax, Giáo trình tin học lý thuyết. OpenStax CNX. Jul 30, 2009 Download for free at http://cnx.org/content/col10826/1.1
Google Play and the Google Play logo are trademarks of Google Inc.

Notification Switch

Would you like to follow the 'Giáo trình tin học lý thuyết' conversation and receive update notifications?

Ask