'''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 [[Máy Turing|hàm tính toán Turing]] và các [[hàm đệ quy-M]].
'''CácTrước định nghĩa chính xác của hàm tính toán, được'''các là[[nhà cáctoán đốihọc]] tượngthường nghiênsử cứudụng cơthuật bảnngữ trongkhông [[lýchính thuyếtthức ''có thể tính toán]] một cách hiệu quả''. CácThuật hàmngữ này đã được xác định với các chức năng tính toán. làLưu sựý tươngrằng tựkhả chínhnăng thứctính củatoán kháihiệu niệmquả trựccủa quancác củachức [[thuậtnăng toán]],này theokhông có nghĩa là một hàmchúng có thể được tính toán đượcmột nếu''cách tồnhiệu tạiquả'' một(nghĩa thuật toánlà có thể thựctính hiệnđược côngtrong việcmột củakhoảng hàm,thời tứcgian làhợp đưalý). raTrong mộtthực sốtế, đầuđối vàovới thuộcmột miền xác định củasố hàm, nó có thể trảtính vềtoán kếthiệu quả, đầucó rathể tươngchỉ ứng.ra Cácrằng chứcbất năngkỳ tínhthuật toán đượcnào sửtính dụngtoán đểchúng thảosẽ luậnrất vềkém khảhiệu năngquả tínhtheo toánnghĩa màlà khôngthời cầngian thamchạy khảocủa bấtthuật kỳtoán [[môtăng hìnhtrưởng tínhtheo toáncấp số nhân]] cụ(hoặc thểthậm nàochí nhưlà [[máyTúc Turing]]thừa|siêu hoặccấp [[máy thanhsố ghinhân]]) .với Tuyđộ nhiên,dài bấtcủa kỳđầu địnhvào. nghĩaCác nàolĩnh cũngvực phải[[Lý thamthuyết chiếuđộ đếnphức mộttạp số mô hìnhtính toán|tính toán cụkhả thểthi]] nhưngvà tất[[Lý cảthuyết cácđộ địnhphức nghĩatạp hợptính lệtoán|độ đềuphức mang lại cùng một lớp hàm. Các mô hình đặc biệt về khả năngtạp tính toán]] tạonghiên ra tập hợpcứu các hàm tínhmà toáncó là các [[Máy Turing|hàmthể tính toán Turing]]được vàmột cáccách [[hàm đệ quy-M]]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.▼
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à [[Túc thừa|siêu cấp số nhân]] ) với độ dài của đầu vào. Các lĩnh vực [[Lý thuyết độ phức tạp tính toán|tính toán khả thi]] và [[Lý thuyết độ phức tạp tính toán|độ 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ả.
==Tham khảo==
▲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.
