Luận điểm của Church-Turing đề cập đến khái niệm về một phương pháp hiệu quả, có hệ thống hoặc cơ học trong logic, toán học và khoa học máy tính. Nó được xây dựng dưới dạng mô tả khái niệm trực quan về khả năng tính toán và liên quan đến các hàm đệ quy tổng quát, thường được gọi là luận điểm của Church. Nó cũng đề cập đến lý thuyết về các chức năng máy tính có thể tính toán được. Luận điểm xuất hiện vào những năm 1930, khi bản thân máy tính vẫn chưa tồn tại. Sau đó nó được đặt theo tên của nhà toán học người Mỹ Alonso Church và đồng nghiệp người Anh của ông Alan Turing.
Hiệu quả của phương pháp để đạt được kết quả
Thiết bị đầu tiên giống máy tính hiện đại là Bombie, một cỗ máy do nhà toán học người Anh Alan Turing tạo ra. Nó được sử dụng để giải mã các thông điệp của Đức trong Thế chiến thứ hai. Nhưng đối với luận điểm của mình và hình thức hóa khái niệm thuật toán, ông đã sử dụng các máy trừu tượng, sau này được gọi là máy Turing. Luận văn trình bàysự quan tâm của cả nhà toán học và lập trình viên, vì ý tưởng này đã truyền cảm hứng cho những người tạo ra những chiếc máy tính đầu tiên.
Trong lý thuyết tính toán, luận điểm Church-Turing còn được gọi là phỏng đoán về bản chất của các hàm tính toán. Nó tuyên bố rằng đối với bất kỳ hàm có thể tính toán theo thuật toán nào trên các số tự nhiên, có một máy Turing có khả năng tính toán nó. Hay nói cách khác, có một thuật toán phù hợp với nó. Một ví dụ nổi tiếng về tính hiệu quả của phương pháp này là kiểm tra bảng chân lý để kiểm tra tính phản xạ.
Một cách để đạt được bất kỳ kết quả mong muốn nào được gọi là "hiệu quả", "có hệ thống" hoặc "cơ học" nếu:
- Phương thức được chỉ định theo số lượng hữu hạn các lệnh chính xác, mỗi lệnh được thể hiện bằng một số ký tự hữu hạn.
- Nó sẽ chạy mà không có lỗi, sẽ tạo ra kết quả mong muốn trong một số bước nhất định.
- Phương pháp này có thể được thực hiện bởi con người mà không cần bất kỳ thiết bị nào khác ngoài giấy và bút chì
- Nó không đòi hỏi sự hiểu biết, trực giác hay sự khéo léo của người thực hiện hành động
Trước đó trong toán học, thuật ngữ không chính thức "có thể tính toán hiệu quả" được sử dụng để chỉ các hàm có thể được tính toán bằng bút chì và giấy. Nhưng khái niệm về khả năng tính toán theo thuật toán trực quan hơn bất cứ điều gì cụ thể. Bây giờ nó được đặc trưng bởi một hàm có đối số tự nhiên, mà có một thuật toán tính toán. Một trong những thành tựu của Alan Turing làđại diện của một vị từ chính xác về mặt hình thức, với sự trợ giúp của nó, có thể thay thế vị ngữ không chính thức, nếu điều kiện hiệu quả của phương thức được sử dụng. Church đã khám phá ra điều tương tự.
Các khái niệm cơ bản về hàm đệ quy
Việc thay đổi vị ngữ củaTuring thoạt nhìn có vẻ khác với sự thay đổi vị ngữ do đồng nghiệp của anh ấy đề xuất. Nhưng kết quả là chúng trở nên tương đương, theo nghĩa là mỗi người trong số chúng chọn cùng một tập các hàm toán học. Luận điểm Church-Turing là khẳng định rằng tập hợp này chứa mọi hàm mà các giá trị của nó có thể nhận được bằng một phương pháp thỏa mãn các điều kiện hiệu quả. Có một sự khác biệt giữa hai khám phá. Đó là Church chỉ xem xét các ví dụ về số nguyên dương, trong khi Turing mô tả công việc của mình là bao gồm các hàm có thể tính toán với một biến tích phân hoặc thực.
Các hàm đệ quy thông dụng
Công thức ban đầu của Church nói rằng phép tính có thể được thực hiện bằng cách sử dụng phép tính λ. Điều này tương đương với việc sử dụng các hàm đệ quy chung. Luận điểm của Church-Turing đề cập đến nhiều loại tính toán hơn so với suy nghĩ ban đầu. Ví dụ: liên quan đến tự động dữ liệu di động, bộ tổ hợp, máy đăng ký và hệ thống thay thế. Năm 1933, các nhà toán học Kurt Gödel và Jacques Herbrand đã tạo ra một định nghĩa chính thức về một lớp gọi là các hàm đệ quy tổng quát. Nó sử dụng các hàm trong đó có thể có nhiều hơn một đối số.
Tạo phương phápλ-tích
Năm 1936, Nhà thờ Alonso đã tạo ra một phương pháp xác định được gọi là phép tính λ. Ông đã liên kết với các số tự nhiên. Trong phép tính λ, nhà khoa học đã xác định mã hóa của chúng. Do đó, chúng được gọi là số Giáo hội. Một hàm dựa trên các số tự nhiên được gọi là λ-computable. Có một định nghĩa khác. Hàm theo luận điểm của Church được gọi là λ-computable trong hai điều kiện. Điều kiện đầu tiên nghe có vẻ như thế này: nếu nó được tính toán trên các phần tử của Church, và điều kiện thứ hai là khả năng được đại diện bởi một thành viên của phép tính λ.
Cũng vào năm 1936, trước khi nghiên cứu công việc của đồng nghiệp, Turing đã tạo ra một mô hình lý thuyết cho các máy trừu tượng ngày nay mang tên ông. Họ có thể thực hiện các phép tính bằng cách thao tác các ký tự trên băng. Điều này cũng áp dụng cho các hoạt động toán học khác được tìm thấy trong khoa học máy tính lý thuyết, chẳng hạn như tính toán xác suất lượng tử. Chức năng từ luận điểm của Church sau này chỉ được chứng minh bằng máy Turing. Ban đầu, họ dựa vào phép tính λ.
Tính toán hàm
Khi các số tự nhiên được mã hóa thích hợp dưới dạng chuỗi ký tự, một hàm trên số tự nhiên được cho là có thể tính toán Turing nếu máy trừu tượng tìm ra thuật toán cần thiết và in hàm này ra băng. Một thiết bị như vậy, không tồn tại vào những năm 1930, trong tương lai sẽ được coi là một máy tính. Máy Turing trừu tượng và luận điểm của Church báo trước một kỷ nguyên phát triểnThiết bị tính toán. Nó đã được chứng minh rằng các lớp của chức năng được xác định chính thức bởi cả hai nhà khoa học là trùng hợp. Do đó, kết quả là cả hai câu lệnh đã được kết hợp thành một. Các hàm tính toán và luận điểm của Church cũng có ảnh hưởng mạnh mẽ đến khái niệm tính toán được. Chúng cũng trở thành một công cụ quan trọng cho logic toán học và lý thuyết chứng minh.
Biện minh và các vấn đề của phương pháp
Có nhiều quan điểm trái ngược nhau về luận điểm. Nhiều bằng chứng đã được thu thập cho "giả thuyết hoạt động" do Church và Turing đề xuất vào năm 1936. Nhưng tất cả các phương pháp hoặc hoạt động đã biết để khám phá các chức năng mới có thể tính toán hiệu quả từ những chức năng đã cho đều được kết nối với các phương pháp xây dựng máy móc, khi đó chưa tồn tại. Để chứng minh luận điểm của Church-Turing, người ta bắt đầu từ thực tế rằng mọi mô hình tính toán thực tế đều tương đương.
Do có nhiều phân tích khác nhau, đây thường được coi là bằng chứng đặc biệt mạnh mẽ. Tất cả những nỗ lực nhằm xác định chính xác hơn khái niệm trực quan về một hàm có thể tính toán hiệu quả hóa ra là tương đương. Mọi phân tích đã được đề xuất đã được chứng minh là chỉ ra cùng một lớp hàm, cụ thể là những hàm có thể tính toán được bằng máy Turing. Nhưng một số mô hình tính toán hóa ra lại hiệu quả hơn về thời gian và sử dụng bộ nhớ cho các tác vụ khác nhau. Sau đó, người ta lưu ý rằng các khái niệm cơ bản của hàm đệ quy và luận điểm của Church là khá giả thuyết.
Luận văn M
Điều quan trọng là phải phân biệt giữa luận điểm của Turing và khẳng định rằng bất cứ thứ gì có thể tính được bằng thiết bị máy tính đều có thể được tính bằng máy của nó. Tùy chọn thứ hai có định nghĩa riêng của nó. Gandhi gọi câu thứ hai là "Thesis M". Nó diễn ra như thế này: “Bất cứ thứ gì có thể được tính toán bởi một thiết bị đều có thể được tính toán bởi một máy Turing.” Theo nghĩa hẹp của luận điểm, nó là một mệnh đề thực nghiệm mà giá trị chân lý của nó chưa được biết đến. Turing's Thesis và "Thesis M" đôi khi bị nhầm lẫn. Phiên bản thứ hai nói chung là không chính xác. Các máy có điều kiện khác nhau đã được mô tả có thể tính toán các hàm không thể tính toán Turing. Điều quan trọng cần lưu ý là luận điểm đầu tiên không liên quan đến luận điểm thứ hai, nhưng phù hợp với tính sai lệch của nó.
Hàm ý ngược lại của luận điểm
Trong lý thuyết tính toán, luận điểm của Church được sử dụng như một mô tả về khái niệm tính toán được bởi một lớp các hàm đệ quy tổng quát. Stephen Kleene người Mỹ đã đưa ra một công thức tổng quát hơn. Ông gọi là đệ quy một phần tất cả các hàm từng phần có thể tính toán được bằng các thuật toán.
Hàm ý ngược thường được gọi là luận điểm ngược của Church. Nó nằm ở chỗ mọi hàm đệ quy của số nguyên dương đều được đánh giá một cách hiệu quả. Theo nghĩa hẹp, một luận điểm chỉ đơn giản biểu thị một khả năng như vậy. Và theo nghĩa rộng hơn, nó tóm tắt từ câu hỏi liệu chiếc máy có điều kiện này có thể tồn tại trong đó hay không.
Máy tính lượng tử
Các khái niệm về hàm tính toán và luận điểm của Church đã trở thành một khám phá quan trọng đối với toán học, lý thuyết máy và nhiều ngành khoa học khác. Nhưng công nghệ đã thay đổi rất nhiều và tiếp tục cải tiến. Người ta cho rằng máy tính lượng tử có thể thực hiện nhiều tác vụ thông thường với ít thời gian hơn máy tính hiện đại. Nhưng câu hỏi vẫn còn, chẳng hạn như vấn đề dừng lại. Máy tính lượng tử không thể trả lời nó. Và, theo luận điểm của Church-Turing, không có thiết bị máy tính nào khác.
