Câu hỏi 86
Trong bài toán này, ta khảo sát các hàm trên tập số tự nhiên có thể được tính bởi một máy tính (có bộ nhớ và đầu ra hữu hạn) cho các số lớn tùy ý. Các hàm này được gọi là các hàm tính được (Computable Functions). Vì máy tính chỉ có một số hữu hạn đầu ra nên ta chỉ xét những hàm có tập giá trị hữu hạn (điều này tương đương với việc xét mọi đầu ra hữu hạn có thể có của một máy tính). Tiếp theo, cần làm rõ cách đưa một số vào máy tính. Một cách phổ biến là dùng biểu diễn của số trong một cơ số $k$ cố định.
Bằng cách xác định các đầu vào và đầu ra của một máy tính, ta có thể xây dựng một mô hình toán học mô tả hoạt động của nó (tức là mô hình hóa nó). Ý chính ở đây là một máy tính có một số hữu hạn trạng thái (xét trạng thái của mọi thành phần bên trong) và nó thay đổi sau khi nhận mỗi chữ số đầu vào theo một chương trình định sẵn. Do đó, đầu ra là một hàm của trạng thái của máy tính. Từ các khái niệm này, ta có thể đưa ra định nghĩa chính xác về dãy $k$-Computable.
Trước hết cần định nghĩa một Máy (Machine). Một Máy với tập đầu vào $A$ và tập đầu ra $B$ (các tập $A$ và $B$ hữu hạn) gồm một số hữu hạn trạng thái và một thuật toán xác định trạng thái của Máy sau khi nhập một đầu vào (là một phần tử bất kỳ của $A$). Ngoài ra, mỗi trạng thái của Máy xác định một phần tử của $B$ làm đầu ra. Hơn nữa, một trạng thái đặc biệt, gọi là Trạng thái bắt đầu (Starting State), được dùng để khởi động Máy. Một Máy như vậy có thể xác định một phần tử của $B$ làm đầu ra cho một dãy hữu hạn các đầu vào từ $A$. Việc này được thực hiện bằng cách đặt Máy ở Trạng thái bắt đầu rồi nhập lần lượt từng phần tử của dãy. Đầu ra của trạng thái cuối cùng được xem là giá trị được tính.
Cho $k$ là một số tự nhiên lớn hơn $1$. Một dãy $a_1, a_2, a_3, \dots$ với các giá trị thuộc tập hữu hạn $B$ được gọi là $k$-Computable nếu tồn tại một Máy với tập đầu vào $\{0, 1, \dots, k-1\}$ và tập đầu ra $B$ sao cho khi các chữ số của một số $n$ bất kỳ trong cơ số $k$ được nhập vào Máy lần lượt từ phải sang trái thì đầu ra của Máy là $a_n$.
Để làm ví dụ, xét Máy sau cho $k=2$ (các hình tròn biểu diễn các trạng thái và đầu ra của mỗi trạng thái được viết trên nó. Máy này nhận $0$ và $1$ làm đầu vào).
Dùng Máy này có thể tính dãy $a, b, a, a, a, b, a, b, \dots$. Chẳng hạn, với $n = 10 = (1010)_2$, ta cần nhập $0$, $1$, $0$ và $1$ vào Máy, bắt đầu từ Trạng thái bắt đầu. Khi làm như vậy, ta đến trạng thái ở dưới bên trái, có đầu ra là $a$. Theo định nghĩa, dãy $a, b, a, a, a, b, a, b, \dots$ là $2$-Computable.
a) Giả sử $m$ là một số tự nhiên. Với mỗi số tự nhiên $n$, định nghĩa $(a_n)$ là số dư của $n$ khi chia cho $m$ (do đó các giá trị của dãy này đều thuộc tập hữu hạn $\{0, 1, \dots, m-1\}$). Chứng minh rằng với mỗi số tự nhiên $k$, dãy này là $k$-Computable.
b) Chứng minh rằng nếu dãy $(a_n)$ là $k$-Computable thì các dãy $(b_n)$ và $(c_n)$ xác định bởi $b_n = a_{n+1}$ và $c_n = a_{2n}$ cũng là $k$-Computable.
c) Định nghĩa dãy $(a_n)$ bằng $1$ tại các số tự nhiên là số chính phương và bằng $0$ tại các số còn lại. Dãy này có là $3$-Computable hay không?
d) Định nghĩa dãy Computable có thể được thay đổi bằng cách giả sử các chữ số được nhập vào Máy từ trái sang phải. Các dãy này được gọi là $k$-Left Computable. Chứng minh rằng định nghĩa này tương đương với định nghĩa trước, tức là một dãy là $k$-Computable khi và chỉ khi nó là $k$-Left Computable.
Bằng cách xác định các đầu vào và đầu ra của một máy tính, ta có thể xây dựng một mô hình toán học mô tả hoạt động của nó (tức là mô hình hóa nó). Ý chính ở đây là một máy tính có một số hữu hạn trạng thái (xét trạng thái của mọi thành phần bên trong) và nó thay đổi sau khi nhận mỗi chữ số đầu vào theo một chương trình định sẵn. Do đó, đầu ra là một hàm của trạng thái của máy tính. Từ các khái niệm này, ta có thể đưa ra định nghĩa chính xác về dãy $k$-Computable.
Trước hết cần định nghĩa một Máy (Machine). Một Máy với tập đầu vào $A$ và tập đầu ra $B$ (các tập $A$ và $B$ hữu hạn) gồm một số hữu hạn trạng thái và một thuật toán xác định trạng thái của Máy sau khi nhập một đầu vào (là một phần tử bất kỳ của $A$). Ngoài ra, mỗi trạng thái của Máy xác định một phần tử của $B$ làm đầu ra. Hơn nữa, một trạng thái đặc biệt, gọi là Trạng thái bắt đầu (Starting State), được dùng để khởi động Máy. Một Máy như vậy có thể xác định một phần tử của $B$ làm đầu ra cho một dãy hữu hạn các đầu vào từ $A$. Việc này được thực hiện bằng cách đặt Máy ở Trạng thái bắt đầu rồi nhập lần lượt từng phần tử của dãy. Đầu ra của trạng thái cuối cùng được xem là giá trị được tính.
Cho $k$ là một số tự nhiên lớn hơn $1$. Một dãy $a_1, a_2, a_3, \dots$ với các giá trị thuộc tập hữu hạn $B$ được gọi là $k$-Computable nếu tồn tại một Máy với tập đầu vào $\{0, 1, \dots, k-1\}$ và tập đầu ra $B$ sao cho khi các chữ số của một số $n$ bất kỳ trong cơ số $k$ được nhập vào Máy lần lượt từ phải sang trái thì đầu ra của Máy là $a_n$.
Để làm ví dụ, xét Máy sau cho $k=2$ (các hình tròn biểu diễn các trạng thái và đầu ra của mỗi trạng thái được viết trên nó. Máy này nhận $0$ và $1$ làm đầu vào).
Dùng Máy này có thể tính dãy $a, b, a, a, a, b, a, b, \dots$. Chẳng hạn, với $n = 10 = (1010)_2$, ta cần nhập $0$, $1$, $0$ và $1$ vào Máy, bắt đầu từ Trạng thái bắt đầu. Khi làm như vậy, ta đến trạng thái ở dưới bên trái, có đầu ra là $a$. Theo định nghĩa, dãy $a, b, a, a, a, b, a, b, \dots$ là $2$-Computable.
a) Giả sử $m$ là một số tự nhiên. Với mỗi số tự nhiên $n$, định nghĩa $(a_n)$ là số dư của $n$ khi chia cho $m$ (do đó các giá trị của dãy này đều thuộc tập hữu hạn $\{0, 1, \dots, m-1\}$). Chứng minh rằng với mỗi số tự nhiên $k$, dãy này là $k$-Computable.
b) Chứng minh rằng nếu dãy $(a_n)$ là $k$-Computable thì các dãy $(b_n)$ và $(c_n)$ xác định bởi $b_n = a_{n+1}$ và $c_n = a_{2n}$ cũng là $k$-Computable.
c) Định nghĩa dãy $(a_n)$ bằng $1$ tại các số tự nhiên là số chính phương và bằng $0$ tại các số còn lại. Dãy này có là $3$-Computable hay không?
d) Định nghĩa dãy Computable có thể được thay đổi bằng cách giả sử các chữ số được nhập vào Máy từ trái sang phải. Các dãy này được gọi là $k$-Left Computable. Chứng minh rằng định nghĩa này tương đương với định nghĩa trước, tức là một dãy là $k$-Computable khi và chỉ khi nó là $k$-Left Computable.