Giả thuyế church
Giả thuyết rằng khái niệm trực giác “Hàm tính được” (computable function) có thể được định nghĩa bằng lớp các hàm đệ quy bộ phận là giả thuyết Church hay còn được gọi là luận đề Church - Turing. Trong khi chúng ta không thể hy vọng ...
Giả thuyết rằng khái niệm trực giác “Hàm tính được” (computable function) có thể được định nghĩa bằng lớp các hàm đệ quy bộ phận là giả thuyết Church hay còn được gọi là luận đề Church - Turing. Trong khi chúng ta không thể hy vọng để chứng minh giả thuyết Church cũng như những định nghĩa không hình thức về “sự tính được”, chúng ta có thể cho những dẫn chứng về những khả triển của chúng. Trong một thời gian dài, khái niệm trực giác về “sự tính được” đặt không giới hạn trên số bước hoặc tổng số các lưu trữ, có vẻ như các hàm đệ quy bộ phận thì có thể tính được một cách trực giác mặc dù cũng có một số hàm không thể tính được trừ khi ta đặt giới hạn cho việc tính toán sau đó hoặc ít nhất thiết lập được liệu có hay không có phép tính cuối cùng.
Điều còn không rõ là liệu lớp các hàm đệ quy bộ phận có thể bao hàm tất cả mọi “hàm tính được”. Những nhà logic học đã đưa ra nhiều công thức khác, chẳng hạn như phép tính-λ, hệ thống Post và các hàm đệ quy tổng quát. Tất cả chúng được định nghĩa cùng một lớp hàm, cụ thể là hàm đệ quy bộ phận. Hơn nữa, các mô hình máy tính trừu tượng, chẳng hạn như mô hình RAM (Random Access Machine) cũng được xem xét như một hàm đệ quy bộ phận.
Mô hình RAM bao gồm một số vô hạn các từ nhớ, đánh số 0, 1, ..., mỗi một từ nhớ có thể lưu giữ một số nguyên bất kỳ và một số hữu hạn các thanh ghi số học cũng có khả năng giữ các số nguyên bất kỳ. Các số nguyên có thể được giải mã thành các dạng thông thường của các chỉ thị máy tính. Chúng ta sẽ không định nghĩa mô hình RAM một cách hình thức hơn, nhưng sẽ rõ ràng hơn nếu chúng ta chọn một tập các chỉ thị phù hợp, RAM sẽ mô phỏng mọi máy tính hiện có. Chứng minh rằng mô hình máy Turing cũng có khả năng tương đương như mô hình RAM được chỉ ra dưới đây hay có thể nói một máy Turing cũng có tác dụng như một kiểu RAM.
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.