Luận đề Church-Turing

Tập tin:File:Model of a Turing machine.jpg

Một phiên bản máy Turing

Luận đề Church-Turing khẳng định “bất kì hàm nào tính được bằng một thuật toán thì cũng tính được bằng máy Turing”.

Nói một cách cụ thể, nếu một việc có thể được thực hiện bởi một thuật toán, thì tồn tại một máy Turing thực hiện việc này. Khẳng định ngược lại là dễ thấy: bản thân mỗi máy Turing là một thuật toán.

Bài toán quyết định của Hilbert và Thuật toán

Luận đề Church-Turing được đưa ra vào năm 1936 trong các bài báo độc lập của Alonzo Church và Alan Turing. Mục đích của Church và Turing nhằm giải quyết Bài toán Quyết định của David Hilbert. Nói một cách đơn giản, bài toán có thể được phát biểu như sau: Tìm một thủ tục hiệu quả để quyết định xem một phát biểu toán học là đúng hay sai khi cho trước một tập tiên đề và các luật suy luận.

Thủ tục hiệu quả mà Hilbert đề cập là “thủ tục” theo nghĩa kinh điển của toán học, giống như Thuật toán Euclid để tìm ước chung lớn nhất của hai số nguyên dương hay Thuật toán sàng Eratosthenes để tìm các số nguyên tố. Về trực giác, thủ tục M thực hiện một nhiệm vụ nào đó được gọi là “hiệu quả”nếu nó thỏa mãn bốn tính chất sau:

1. M được đưa ra dưới dạng một số hữu hạn các chỉ dẫn chính xác (mỗi chỉ dẫn có thể biểu diễn dưới dạng một số hữu hạn ký hiệu);
2. Nếu không bị lỗi, M sẽ luôn cho kết quả mong đợi sau một số hữu hạn bước;
3. M có thể (trong thực tế hoặc về nguyên tắc) được thực hiện bởi con người với giấy và bút mà không cần sự giúp đỡ của máy móc;
4. M không yêu cầu người thực hiện phải có một trực giác sâu sắc hoặc một tài năng đặc biệt nào.

Về mặt thuật ngữ, thủ tục hiệu quả chính là khái niệm thuật toán theo nghĩa trực giác.

Luận đề Church

Để giải bài toán của Hilbert, Church sáng tạo ra hệ thống ký hiệu gọi là phép tính lambda (λ-calculus). Các phép tính này sau đó được Stephen Kleene chứng minh là tương đương với khái niệm hàm đệ qui Herbrand-Gödel (hay ngắn gọn là hàm đệ quy). Với kết quả này Church tin tưởng rằng:

Luận đề Church: Mọi hàm tính được (bằng thuật toán) đều là hàm đệ quy.

Chú ý rằng “luận đề” có ý nghĩa như một định nghĩa, một tiên đề, không cần phải chứng minh. Vấn đề là ta có tin rằng các hàm đệ qui nắm bắt được mấu chốt của khái niệm thuật toán hay không mà thôi.

Luận đề Turing

Turing sáng tạo ra mọt mô hình "máy" để hình thức hóa khái niệm thuật toán. Máy này, thường được gọi là máy Turing, đuợc thiết kế để bắt chuớc quá trình tính toán của con nguời. Turing đã phân tích rất chi tiết các hành vi tính toán của con người để thuyết phục rằng máy Turing nắm bắt được khái niệm thuật toán.

Luận đề Turing: Mọi hàm tính được (bằng thuật toán) đều là hàm tính được bởi máy Turing.

Hơn nữa, Turing chứng minh rằng các hàm tính được bởi máy Turing và bởi phép tính lambda là trùng nhau. Do đó luận đề của Church và luận đề của Turing có ý nghĩa tương đương và thường được gọi chung đó là luận đề Church-Turing.

Máy Turing

Ngày nay, máy Turing được thừa nhận rộng rãi như một mô hình toán học của máy tính. Tuy nhiên, cần nhấn mạnh rằng, tại thời điểm mà Turing giới thiệu máy của mình, máy tính chưa xuất hiện. Trên thực tế, Turing đã thiết kế máy nhằm mô phỏng hành vi tính toán của con người chứ không phải của máy tính.

Trong bài báo nổi tiếng của mình, Turing đã xem xét các hành vi tính toán của con người và chắt lọc ra các yếu tố căn bản nhất. Ông nhận thấy rằng yếu tố quan trọng của quá trình tính toán chỉ bao gồm việc đọc và viết các ký hiệu đơn giản. Ông viết:

Việc tính toán thường được thực hiện bằng cách viết các ký hiệu nào đó lên giấy. Ta có thể giả sử rằng giấy viết được chia thành các ô giống như trong sách số học của trẻ em. Hành vi tính toán tại một thời điểm bất kỳ được xác định bởi các ký hiệu mà người thực hiện tính toán quan sát được và “trạng thái nhận thức” (states of mind) của anh ta tại thời điểm đó.

Ta hãy tưởng tượng các thao tác tính toán thực hiện bởi con người sẽ được chia thành các “thao tác đơn giản”mà cơ bản đến mức không dễ tưởng tượng chúng lại có thể chia nhỏ hơn nữa. Mỗi thao tác như vậy gây ra một vài sự thay đổi hệ thống vật lý bao gồm cả người thực hiện tính toán và băng giấy của anh ta... Ta có thể giả sử rằng trong một thao tác đơn giản chỉ có nhiều nhất một ký hiệu bị thay đổi. Những thay đổi khác có thể được chia nhỏ thành một số thay đổi dạng này.

Dù giấy viết mà chúng ta sử dụng là hai chiều, Turing nhận thấy rằng dùng băng giấy một chiều là đủ. Giấy viết (hai chiều) có thể mô phỏng bởi băng giấy một chiều. Mỗi ô trên băng giấy sẽ chứa một ký hiệu. Bảng chữ cái của ký hiệu trên băng là hữu hạn vì con người chỉ có thể phân biệt một số hữu hạn ký hiệu khác nhau. Hơn nữa, Turing giả sử các “trạng thái nhận thức” của con người cũng là một tập hữu hạn. Ông giải thích:

Người thực hiện tính toán luôn có thể dừng việc tính toán để làm việc khác, quên đi toàn bộ quá trình tính toán đã thực hiện, và sau đó có thể quay lại và tiếp tục công việc tính toán này. Để làm được điều này, anh ta phải ghi lại các chỉ dẫn (được viết ở dạng chuẩn) để giải thích cách tiếp tục công việc. Ghi chú này phải bao gồm cả trạng thái nhận thức của anh ta. Ta giả sử rằng người thực hiện tính toán có năng lực hạn chế đến mức mỗi lần anh ta chỉ có thể thực hiện một bước tính toán. Các chỉ dẫn được ghi lại sẽ cho phép anh ta thực hiện một bước tính toán và viết ra chỉ dẫn cho bước tiếp theo. Do đó, trạng thái của quá trình tính toán tại mọi giai đoạn hoàn toàn được xác định bởi việc ghi lại các chỉ dẫn và các ký hiệu trên băng.

Dựa vào những phân tích ở trên, máy Turing được mô tả như sau. Máy có một đầu đọc-viết, có một số hữu hạn trạng thái bên trong, và có một băng tuyến tính được xem là vô hạn về bên phải để lưu thông tin. Băng này được chia thành các ô, mỗi ô chứa một ký hiệu thuộc một bảng chữ cái hữu hạn. Tại mỗi bước tính toán, máy quan sát ký hiệu tại vị trí hiện tại trên băng. Dựa trên ký hiệu này và trạng thái bên trong, máy thực hiện

1. Cập nhật ký hiệu tại vị trí hiện tại trên băng;
2. Cập nhật trạng thái bên trong; và
3. Di chuyển một bước sang phải hoặc trái trên băng.

Nếu ta ký hiệu $\Gamma$ là bảng chữ cái của ký hiệu trên băng, và ký hiệu Q là tập trạng thái bên trong của máy, thì hành vi của máy có thể viết như một hàm chuyển,

$\delta :{\text{Q}}\times \Gamma \rightarrow {\text{Q}}\times \Gamma \times \{{\text{L, R}}\}$

Ở đây L, R là hai ký hiệu đặc biệt để điều khiển việc di chuyển đầu đọc-viết sang trái (L) hoặc sang phải (R). Ví dụ, $\delta (q,a)=(r,b,L)$ có nghĩa rằng: nếu máy nhìn ký hiệu a trên băng khi nó đang ở trạng thái q, thì nó sẽ cập nhật ký hiệu trên băng thành b, chuyển sang trạng thái r, và chuyển đầu đọc-viết sang trái.

Khởi đầu, máy đặt xâu vào w=w₁ w₂...w_n trên n ô trái nhất của băng, và phần còn lại của băng chứa toàn ký hiệu trắng; đầu đọc-viết được đặt ô trái nhất của băng; và máy ở một trạng thái gọi là trạng thái khởi đầu.

Trong quá trình tính toán, máy thực hiện tính toán theo các luật được mô tả bởi hàm chuyển. Máy sử dụng băng như không gian làm việc: đọc và viết các ký hiệu trên băng. Các ký hiệu trên băng biểu diễn kết quả trung gian của quá trình tính toán. Máy sẽ tính toán cho đến khi đạt đến một trạng thái đặc biệt gọi là trạng thái dừng. Khi đó, các ký hiệu còn lại trên băng chính là kết quả tính toán.

Lịch sử vấn đề

Các nhà toán học đã nghiên cứu về thuật toán từ rất sớm. Ví dụ thuật toán Euclid tìm ước chung lớn nhất của hai số nguyên dương đã xuất hiện từ 300 năm trước Công nguyên. Dù vậy, trước năm 1930, người ta không quan tâm đến việc hình thức hóa khái niệm thuật toán. Các nhà toán học đã xem việc tồn tại thuật toán là hiển nhiên. David Hilbert đã kêu gọi việc tìm lời giải thuật toán cho một số bài toán cụ thể, như bài toán thứ mười về tìm nghiệm nguyên của phương trình Diophantine, hay bài toán quyết định (Entscheidungsproblem) về việc kiểm tra một phát biểu toán học là đúng hay sai khi cho trước một tập các tiên đề và các luật suy luận.

Tuy nhiên, năm 1930, Kurt Gödel đã chứng minh “Định lý bất toàn”. Định lý khẳng định rằng bất kì một hệ tiên đề hình thức độc lập nào đủ mạnh để miêu tả số học cũng hàm chứa những mệnh đề không thể khẳng định mà cũng không thể phủ định. Định lý này dấy lên mối nghi ngờ về sự tồn tại thuật toán cho bài toán quyết định của Hilbert.

Để nghiên cứu bài toán quyết định, Alonzo Church và học trò của ông là Stephen Kleene sáng tạo ra phép tính lambda, từ đó giới thiệu lớp hàm định nghĩa bởi phép tính lambda, gọi là λ-định nghĩa được. Họ đã chỉ ra rằng rất nhiều lớp hàm thường gặp trong lý thuyết số là λ-định nghĩa được.

Church và Gödel thảo luạn về phép tính lambda ở Đại học tổng hợp Princeton. Church đã gợi ý với Gödel rằng nên định nghĩa các hàm tính bởi thuật toán (hay ngắn gọn là hàm tính được) là các hàm λ-định nghĩa được. Gödel không thấy bị thuyết phục bởi ý tưởng này. Ông gợi ý rằng khái niệm “thuật toán” nên được tiên đề hóa. Tuy nhiên, thay vì đưa ra một hệ tiên đề, Gödel lại cải tiến mọt ý tuởng của Jacques Herbrand để tạo nen các hàm đệ qui Herbrand-Gödel, gọi ngắn gọn là các hàm đệ quy. Sau đó, Kleene đã chứng minh rằng các phép tính lambda và các hàm đệ qui là tương đương. Với kết quả này, Church tin rằng các hàm tính được đuợc đều là các hàm đệ quy. Niềm tin này thuờng đuợc gọi là luạn đề Church.

Nam 1936, trong bài báo, Church đã định nghĩa các hàm tính được như là các hàm đệ quy, hay tương đương, là λ-định nghĩa được; và sử dụng định nghĩa này để chứng minh bài toán của Hilbert là không giải được. Ông thiết kế hai biểu thức trong phép tính lambda mà sự tuong đuong của chúng không thể tính đuợc bằng một hàm đệ quy. Nói cách khác, có nhiều phát biểu toán học khong thể chứng minh một cách co học bằng thuật toán.

Cũng vào năm 1936, trong bài báo, Alan Turing cũng chứng minh kết quả tương tự: bài toán của Hilbert là không giải được. Trong bài báo này, ông giới thiệu khái niệm máy Turing và khái niệm “tính được” (computability). Trong phần phụ lục của bài báo nổi tiếng này, Turing chứng minh rằng lớp hàm định nghĩa bởi phép tính lambda và bởi máy Turing là đồng nhất.

Trên thực tế, kết quả của Church hoàn thành trước của Turing khoảng sáu tháng. Sau khi đọc bài báo của Turing, Church đã thừa nhận rằng sự đồng nhất giữa máy Turing và khái niệm thuật toán (không được định nghĩa tường minh) trở nên hiển nhiên ngay lập tức.

Còn Gödel, dù trước đó không bị thuyết phục rằng các hàm tính được đều là hàm đệ quy, sau khi đọc các phân tích của Turing, đã hoàn toàn bị thuyết phục rằng máy Turing chính là khái niệm thuật toán theo nghĩa trực giác.

Thông tin bổ sung

Liệu có thể chứng minh Luận đề Church-Turing? Về lý thuyết, điều này là không thể vì thuật toán theo nghĩa trực giác không phải là một khái niệm toán học chính xác. Tuy nhiên, cho đến nay, thực tiễn luôn chứng minh rằng luận đề đó là đúng đắn; người ta chưa tìm ra được hàm nào tính được (bằng thuật toán) theo một nghĩa trực giác hợp lý nào đó mà không tính được bằng máy Turing. Hơn nữa, một số bằng chứng kinh nghiệm sau đây ủng hộ Luận đề Church-Turing:

1. Đã có nhiều mô hình tính toán khác nhau được đề xuất để hình thức hoá khái niệm thuật toán như “phép tính lambda (λ-calculus) ” của Church, “hàm đệ quy” của Gödel, “máy Turing”, “hệ Post”, và “thuật toán chính quy” của Markov. Tuy nhiên, chúng đều tương đương với máy Turing.
2. Lớp hàm tính được bởi máy Turing có tính bất biến mạnh. Chẳng hạn, hai hàm f (x) và g (x) tính được bởi máy Turing thì hàm tích f (x) g (x) và hàm hợp f (g (x)) cũng tính được bởi máy Turing. Tính bất biến này tương ứng với ý tưởng trực giác rằng nếu ta có thuật toán giải một số bài toán nào đó thì các bài toán nhận được bằng cách “tổ hợp” một cách hợp lý các bài toán này cũng có thuật toán để giải.

Cần nhấn mạnh rằng luận đề Church-Turing liên quan đến thuật toán chứ không phải những gì có thể tính toán bởi các máy vật lý. Trên thực tế, Alan Turing đã thiết kế máy nhằm mô phỏng hành vi tính toán của con người với giấy và bút. Khẳng định “các máy Turing có thể tính toán mọi thứ mà bất kỳ máy tính nào có thể tính toán” là một diễn dịch sai lầm. Bởi vì, trong các thao tác cơ bản thực hiện bởi máy tính vật lý, có những thao tác không thể thực hiện bởi con người chỉ với giấy và bút.

Tài liệu tham khảo

• Alonzo Church. An Unsolvable Problem of Elementary Number Theory. American Journal of Mathematics. 58, 2 (1936). 345–363.

• Alonzo Church. Review: A. M. Turing, On Computable Numbers, with an Application to the Entscheidungsproblem. Journal of Symbolic Logic. 2, 1 (1937). 42–43.

• Jack Copeland. The Church-Turing Thesis, The Stanford Encyclopedia of Philosophy (Spring 2019 Edition). Edward N. Zalta (ed. ).

• Cristopher Moore and Stephan Mertens. The Nature of Computation. Oxford University Press, Inc., New York, NY, USA, 2011.

• Michael Sipser. Introduction to the Theory of Computation. 3rd Ed., Cengage Learning, 2012.

• Alan M. Turing. On Computable Numbers, with an Application to the Entscheidungsproblem, In Proceedings, London Mathematical Society, (1930). 230–265