Hàm đệ quy và Máy ghi

Lý thuyết hàm đệ quy xây dựng các hàm tính toán được từ một số phép toán cơ bản, trong khi máy ghi tính toán với các số nguyên được lưu trữ trong các thanh ghi, hai mô hình này bao quanh máy Turing và xác nhận tính mạnh mẽ của khả năng tính toán.

Definition

Các hàm đệ quy tổng quát là những hàm được xây dựng từ các hằng số, hàm kế tiếp và các phép chiếu bằng cách sử dụng phép hợp thành, đệ quy nguyên thủy và phép cực tiểu hóa không giới hạn; máy ghi là các thiết bị trừu tượng tính toán bằng cách tăng, giảm và kiểm tra nội dung của một tập hợp hữu hạn các thanh ghi chứa các số tự nhiên.

Scope

Chủ đề này bao gồm các hàm đệ quy nguyên thủy, việc bổ sung phép cực tiểu hóa không giới hạn để thu được các hàm đệ quy tổng quát, hàm Ackermann như một hàm tính toán được nhưng không phải là đệ quy nguyên thủy, máy ghi và máy đếm cùng tính phổ quát của chúng, và sự tương đương của tất cả các mô hình này với khả năng tính toán Turing.

Core questions

• Làm thế nào các hàm tính toán được có thể được định nghĩa một cách số học mà không cần bất kỳ máy nào?
• Tại sao phép cực tiểu hóa không giới hạn lại cần thiết ngoài đệ quy nguyên thủy?
• Làm thế nào các máy ghi đơn giản đạt được toàn bộ sức mạnh tính toán?
• Tại sao các mô hình số học và máy này lại trùng khớp với máy Turing?

Key theories

Sự tương đương với khả năng tính toán Turing

Các hàm đệ quy tổng quát và các hàm được tính toán bởi máy ghi chính xác là các hàm tính toán được bằng máy Turing, củng cố luận đề Church–Turing thông qua các mô hình được định nghĩa bằng các thuật ngữ số học thuần túy và máy cơ bản.

Vượt ra ngoài đệ quy nguyên thủy

Hàm Ackermann là hàm tổng quát và tính toán được nhưng tăng trưởng quá nhanh để trở thành đệ quy nguyên thủy, cho thấy rằng tìm kiếm không giới hạn là cần thiết và các hàm đệ quy nguyên thủy là một lớp con thích hợp của các hàm tính toán được.

Tính phổ quát của máy ghi

Minsky đã chỉ ra rằng một máy chỉ với hai bộ đếm và các phép toán tăng, giảm và kiểm tra bằng không đã là Turing-complete, một minh chứng cực đoan về việc tính toán đầy đủ đòi hỏi rất ít cấu trúc.

Clinical relevance

Máy ghi mô hình hóa số học số nguyên của các bộ xử lý thực tế trực tiếp hơn so với băng từ, đệ quy nguyên thủy tương ứng với các chương trình luôn kết thúc và là nền tảng của các ngôn ngữ hàm tổng quát và phân tích kết thúc, và quan điểm hàm đệ quy kết nối tính toán với các nền tảng của toán học.

History

Gödel và Herbrand đã định nghĩa các hàm đệ quy tổng quát vào đầu những năm 1930, và Kleene đã phát triển lý thuyết, bao gồm vai trò của phép cực tiểu hóa. Ackermann trước đó đã trình bày hàm tăng trưởng nhanh của mình, và Minsky đã giới thiệu máy ghi và máy đếm vào những năm 1960, chứng minh ngay cả máy hai bộ đếm cũng có tính phổ quát.

Key figures

• Kurt Gödel
• Stephen Kleene
• Wilhelm Ackermann
• Marvin Minsky

Seminal works

• cutland1980
• minsky1967

Frequently asked questions

Sự khác biệt giữa hàm đệ quy nguyên thủy và hàm đệ quy tổng quát là gì?

Các hàm đệ quy nguyên thủy được xây dựng bằng cách sử dụng các vòng lặp có giới hạn và luôn kết thúc, nhưng chúng không nắm bắt được mọi hàm tính toán được. Việc bổ sung phép cực tiểu hóa không giới hạn, một tìm kiếm có thể chạy vô thời hạn, tạo ra các hàm đệ quy tổng quát, trùng khớp chính xác với các hàm tính toán được bằng máy Turing.

Làm thế nào một máy chỉ với hai bộ đếm có thể mạnh mẽ như một máy tính?

Minsky đã chỉ ra rằng hai thanh ghi chứa các số tự nhiên, chỉ với các phép toán tăng, giảm và kiểm tra bằng không, có thể mô phỏng một máy Turing bằng cách mã hóa băng của nó vào các thanh ghi. Cấu trúc này rất kém hiệu quả, nhưng nó chứng minh rằng phần cứng tối thiểu đã đạt được toàn bộ sức mạnh tính toán.