AFAIK, các số có thể tính toán được là các số có chỉ số i-th có thể được trả về bằng Máy Turing. Vì vậy, một số không thể tính được sẽ giống như một số có dấu thập phân được quyết định nếu một số chương trình khác dừng lại trên một số đầu vào khác, vv Nhưng sau đó một lần nữa, PI là một số thực mà không thể liệt kê bằng T.M. và do đó, không thể tính được? Vậy trường phái tư duy nào là đúng?PI có phải là số tính toán được không?
Có, π được tính toán. Có một vài định nghĩa tương đương về tính toán, nhưng định nghĩa hữu ích nhất ở đây là định nghĩa bạn đã đưa ra ở trên: số thực r được tính nếu có thuật toán để tìm số thứ tự n. Here là một thuật toán như vậy.
Đối số cuối cùng của bạn không phải là âm thanh; bạn đã nhầm lẫn định nghĩa "có thể tìm thấy số n chữ số thứ" có "có thể liệt kê tất cả các chữ số". Cái thứ hai không phải là một định nghĩa hữu ích: nó cũng loại trừ tất cả các sự vô lý và nhiều lý trí nữa!
Một thực tế thú vị là các số tính toán trong thực tế có thể đếm được, vì chúng ta có thể Godel-số máy Turing sản xuất chúng. Do đó hầu như không có thực tế được tính toán.
Tôi nghĩ rằng bạn có nghĩa là hầu như tất cả các số thực là * không * tính được, vì tập hợp các máy Turing có thể đếm được. –
@larsmans: vâng, tất nhiên =) – katrielalex
Cảm ơn bạn đã xóa thông tin đó! Chúc mừng! –
Tôi không hoàn toàn chắc chắn ý bạn là gì bởi "PI là một số thực, không thể liệt kê bằng T.M.". Có, các số thực không phải là số đếm, nhưng tôi không thấy điều này ảnh hưởng đến việc liệu PI có thể tính được hay không. '4' cũng là một số thực, nhưng điều đó không có nghĩa là nó không thể tính toán được. – sepp2k
Um, ý tôi là, tôi nghĩ sẽ mất một Turing Machine vô hạn để tính PI vì bản thân PI là vô cùng dài. –
@Gaurav: bởi đối số đó, nó sẽ mất một máy Turing dài vô hạn để tính toán '1/3', vì' 1/3 = 0.333333 ... 'là vô hạn dài? – katrielalex