Tính không thể thay đổi của một chức năng dựa trên chức năng Busy Beaver
Để cho $\log _b^ac$biểu thị một cơ sở lặp lại-$b$hàm logarit. Ví dụ,$$\log _2^3({2^{65536}}) = {\log _2}({\log _2}({\log _2}({2^{65536}}))) = 4.$$
Chọn một mô hình M tùy ý của máy Turing, giả sử rằng một máy hoạt động với bảng chữ cái gồm hai ký hiệu:$0$ là biểu tượng trống và $1$dưới dạng ký hiệu không trống. Chúng tôi sẽ gọi những cỗ máy như vậy là “M-machine”.
Để cho $f(n)$ biểu thị số lượng ký hiệu không trống tối đa có thể xuất hiện trên băng khi một máy M cụ thể tạm dừng, giả sử rằng tất cả các máy bắt đầu với đầu vào trống và bảng hướng dẫn chứa tối đa $n$ các trạng thái hoạt động.
Sau đó, hàm $F(n)$ được định nghĩa như sau: $${F}(n) = \left\{ \begin{array}{l} 0\quad {\text{if}}\;{x_n}\;{\text{is even}}{\text{,}}\\ 1\quad {\text{if}}\;{x_n}\;{\text{is odd}}{\text{,}} \end{array} \right.$$ Ở đâu $x_n$ là số tự nhiên nhỏ nhất sao cho $$\log _{{f}(n) + 2}^{x_n}({f}(n + 1) + 3) < 2.$$
Câu hỏi: là chức năng $F(n)$ không thể thay đổi đối với bất kỳ mô hình M nào (nghĩa là không tồn tại một máy M có thể tính toán $F(n)$chức năng, không có vấn đề M mà chúng tôi chọn)? Nếu có (hoặc không) thì có chứng minh được điều này không?
CHỈNH SỬA
Giả sử rằng chúng tôi chọn một mô hình được mô tả trong phần "Trò chơi" trong bài viết "Busy Beaver" trên Wikipedia . Là$F$không thể tính được bởi những máy móc như vậy? Tôi cũng quan tâm đến cách chứng minh điều này.
Trả lời
Logarit lồng nhau không thực sự làm được nhiều điều ở đây. Nó là một hàm có thể tính toán được với một nghịch đảo có thể tính toán được, và do đó các hàm$n \mapsto x_n$ và $f$ không chỉ tương đương Turing, mà còn liên quan thông qua tính toán thay đổi tỷ lệ.
Do đó, câu trả lời cho câu hỏi này cũng áp dụng ở đây.
Chúng tôi chắc chắn có thể thiết lập các máy Turing của mình theo cách mà chúng không bao giờ viết tổng số các ký hiệu không trống rơi vào một phạm vi sẽ tạo ra $x_n$kỳ quặc. Chúng tôi cần thực hiện một số phép tính phụ để tìm ra phạm vi có thể chấp nhận được, nhưng với kích thước của phạm vi mà tôi mong đợi rằng các ký hiệu chúng ta cần để xác định khoảng tiếp theo mà chúng ta có thể sử dụng cuối cùng sẽ không đưa chúng ta ra khỏi khoảng.
Mặt khác, đối với một thiết lập tự nhiên, tôi không thấy lý do gì tại sao $F$sẽ có thể tính toán được. Nhưng thực sự để chứng minh điều này cho một thiết lập cụ thể sẽ đòi hỏi suy nghĩ nhiều hơn về các chi tiết của một mô hình máy Turing cụ thể hơn tôi muốn làm.