Turing đã xem xét lại kết quả về giới hạn của chứng minh và tính toán vào năm 1931?
Nguyên lý của máy tính hiện đại lần đầu tiên được mô tả bởi nhà toán học và nhà khoa học máy tính tiên phong Alan Turing, người đã đưa ra ý tưởng trong bài báo nổi tiếng năm 1936, On Computable Numbers. Turing đã tái lập các kết quả năm 1931 của Kurt Gödel về giới hạn của chứng minh và tính toán, thay thế ngôn ngữ hình thức dựa trên số học phổ quát của Gödel bằng các thiết bị giả thuyết chính thức và đơn giản được gọi là máy Turing. Ông đã chứng minh rằng một số máy như vậy sẽ có khả năng thực hiện bất kỳ tính toán toán học có thể tưởng tượng nào nếu nó có thể biểu diễn dưới dạng thuật toán. Ông tiếp tục chứng minh rằng không có lời giải cho bài toán quyết định bằng cách đầu tiên chỉ ra rằng bài toán dừng cho máy Turing là không thể làm sáng tỏ: nói chung, không thể quyết định một cách thuật toán liệu một máy Turing nhất định có bao giờ dừng lại hay không.
Kurt Gödel