Năm 1936, khi chưa có máy tính điện tử nào tồn tại, Alan Turing đã định nghĩa xong thế nào là tính toán được: một băng ô vô hạn, một đầu đọc ghi, và bảng luật dạng đang ở trạng thái này mà đọc thấy ký hiệu kia thì ghi gì, dịch trái hay phải, sang trạng thái nào. Bấy nhiêu đủ để cộng, để kiểm chuỗi đối xứng, để chạy mọi chương trình. Máy ba trạng thái kỷ lục ghi được đúng 6 số 1 trong 13 bước rồi tự dừng, còn câu hỏi một máy bất kỳ có dừng hay không thì Turing chứng minh không thuật toán tổng quát nào trả lời nổi.
Năm 1936, khi chưa có máy tính điện tử nào tồn tại, Alan Turing đã định nghĩa xong thế nào là tính toán được: một băng ô vô hạn, một đầu đọc ghi, và bảng luật dạng đang ở trạng thái này mà đọc thấy ký hiệu kia thì ghi gì, dịch trái hay phải, sang trạng thái nào. Bấy nhiêu đủ để cộng, để kiểm chuỗi đối xứng, để chạy mọi chương trình. Máy ba trạng thái kỷ lục ghi được đúng 6 số 1 trong 13 bước rồi tự dừng, còn câu hỏi một máy bất kỳ có dừng hay không thì Turing chứng minh không thuật toán tổng quát nào trả lời nổi.
Chủ đề liên quan trong Tư duy & Máy