Hàm tính toán được

Các hàm tính toán được là các đối tượng nghiên cứu cơ bản trong lý thuyết tính toán. Các hàm tính toán là sự tương tự chính thức của khái niệm trực quan của thuật toán, theo nghĩa là một hàm có thể tính toán được nếu tồn tại một thuật toán có thể thực hiện công việc của hàm, tức là đưa ra một số đầu vào thuộc miền xác định của hàm, nó có thể trả về kết quả đầu ra tương ứng. Các chức năng tính toán được sử dụng để thảo luận về khả năng tính toán mà không cần tham khảo bất kỳ mô hình tính toán cụ thể nào như máy Turing hoặc máy thanh ghi. Tuy nhiên, bất kỳ định nghĩa nào cũng phải tham chiếu đến một số mô hình tính toán cụ thể nhưng tất cả các định nghĩa hợp lệ đều mang lại cùng một lớp hàm. Các mô hình đặc biệt về khả năng tính toán tạo ra tập hợp các hàm tính toán là các hàm tính toán Turing và các hàm đệ quy-M.

Trước định nghĩa chính xác của hàm tính toán, các nhà toán học thường sử dụng thuật ngữ không chính thức có thể tính toán một cách hiệu quả. Thuật ngữ này đã được xác định với các chức năng tính toán. Lưu ý rằng khả năng tính toán hiệu quả của các chức năng này không có nghĩa là chúng có thể được tính toán một cách hiệu quả (nghĩa là có thể tính được trong một khoảng thời gian hợp lý). Trong thực tế, đối với một số hàm có thể tính toán hiệu quả, có thể chỉ ra rằng bất kỳ thuật toán nào tính toán chúng sẽ rất kém hiệu quả theo nghĩa là thời gian chạy của thuật toán tăng trưởng theo cấp số nhân (hoặc thậm chí là siêu cấp số nhân) với độ dài của đầu vào. Các lĩnh vực tính toán khả thi và độ phức tạp tính toán nghiên cứu các hàm mà có thể tính toán được một cách hiệu quả.

Theo luận văn Church-Turing, các hàm tính toán chính xác là các hàm có thể được tính bằng thiết bị tính toán cơ học với lượng thời gian và không gian lưu trữ không giới hạn. Tương tự, luận án này nói rằng một hàm có thể tính toán được khi và chỉ khi nó có thuật toán. Lưu ý rằng một thuật toán theo nghĩa này được hiểu là một chuỗi các bước mà một người không giới hạn thời gian và với một nguồn cung cấp bút và giấy không giới hạn.

Tham khảo