Các Hàm Tính Toán và Luận đề Church-Turing

Các hàm tính toán là những hàm mà một quy trình cơ học có thể đánh giá, và luận đề Church-Turing xác định khái niệm không chính thức này với một số mô hình toán học chính xác mà tất cả đều định nghĩa cùng một lớp.

Definition

Một hàm được gọi là tính toán được nếu một máy Turing nào đó, hoặc tương đương là một định nghĩa đệ quy từng phần nào đó, tạo ra đầu ra của nó trên mọi đầu vào mà nó được định nghĩa; luận đề Church-Turing khẳng định rằng lớp chính xác về mặt toán học này trùng khớp với lớp trực quan của các hàm có thể tính toán hiệu quả.

Scope

Chủ đề này bao gồm máy Turing, các hàm đệ quy từng phần được xây dựng từ các hàm cơ bản bằng cách kết hợp, đệ quy nguyên thủy và tối thiểu hóa, phép tính lambda và máy đăng ký, các bằng chứng cho thấy các mô hình này tương đương, máy phổ quát và luận đề Church-Turing rằng chúng nắm bắt tất cả các phép tính hiệu quả.

Core questions

• Máy Turing là gì và nó định nghĩa một phép tính như thế nào?
• Các hàm đệ quy từng phần được tạo ra từ các phép toán cơ bản như thế nào?
• Tại sao tất cả các mô hình tính toán hợp lý đều định nghĩa cùng một hàm?
• Tình trạng và ý nghĩa của luận đề Church-Turing là gì?

Key theories

Mô hình máy Turing

Máy Turing là một thiết bị trạng thái hữu hạn hoạt động trên một băng không giới hạn, và các hàm mà nó tính toán chính thức hóa khái niệm thuật toán theo các thao tác ký hiệu cơ bản.

Sự tương đương của các mô hình

Máy Turing, các hàm đệ quy từng phần, phép tính lambda và máy đăng ký đều tính toán chính xác cùng một lớp hàm, chứng tỏ sự mạnh mẽ của khái niệm khả năng tính toán.

Máy phổ quát và liệt kê

Có một máy Turing phổ quát mô phỏng bất kỳ máy nào được cung cấp mã của nó, do đó các hàm tính toán được có thể được liệt kê hiệu quả và được xử lý như dữ liệu, cơ sở của các kết quả tự tham chiếu.

Clinical relevance

Khái niệm về một hàm tính toán được là nền tảng của khoa học máy tính lý thuyết: máy phổ quát báo trước máy tính có chương trình lưu trữ, sự tương đương của các mô hình biện minh cho một định nghĩa thuật toán mạnh mẽ duy nhất, và khuôn khổ cung cấp môi trường chính xác để nghiên cứu tính không quyết định và độ phức tạp.

History

Năm 1936, Church định nghĩa khả năng tính toán hiệu quả thông qua phép tính lambda và Turing thông qua các máy của ông, và hai khái niệm này nhanh chóng được chứng minh là tương đương với các hàm đệ quy của Kleene. Luận đề Church-Turing sau đó trở thành định nghĩa được chấp nhận của thuật toán, và máy phổ quát của Turing trở thành tổ tiên khái niệm của máy tính đa năng.

Key figures

• Alan Turing
• Alonzo Church
• Stephen Cole Kleene
• Emil Post

Seminal works

• cutland1980
• turing1936
• sipser2013

Frequently asked questions

Có một số hàm không tính toán được không?

Có. Bởi vì các chương trình có thể được liệt kê nhưng các hàm thì không, một lập luận đếm cho thấy hầu hết các hàm không tính toán được, và các ví dụ cụ thể như hàm dừng được chứng minh là không tính toán được. Khả năng tính toán là một hạn chế thực sự đối với các hàm mà thuật toán có thể đánh giá.

Luận đề Church-Turing có giới hạn những gì máy tính có thể làm không?

Nó nói rằng không có mô hình tính toán hiệu quả nào mở rộng lớp các hàm tính toán được vượt ra ngoài máy Turing. Phần cứng nhanh hơn hoặc kiến trúc khác nhau thay đổi hiệu quả, chứ không phải giới hạn của những gì có thể tính toán được về nguyên tắc, vì vậy luận đề đặt ra một giới hạn tuyệt đối về khả năng giải quyết bằng thuật toán.