'''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]]”.

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.

Nếu ta ký hiệu <math>\Gamma</math> 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,

<math>\delta : \text{Q} \times \Gamma \rightarrow \text{Q} \times \Gamma \times \{ \text{L, R} \}</math>

Ở đâ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ụ, <math>\delta (q, a) = (r, b, L)</math> 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.

Để 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à &lambda;-đị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 &lambda;-đị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à &lambda;-đị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ó 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.

#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.