Khác biệt giữa bản sửa đổi của “Alan Turing”

Trong bài viết nổi tiếng của ông, tựa đề "Các số khả tính, với áp dụng trong Vấn đề về lựa chọn" (''On Computable Numbers, with an Application to the Entscheidungsproblem'') - thuật toán lôgic - (đệ trình ngày [[28 tháng 5]] năm [[1936]]), Turing tái dựng lại kết quả của [[Kurt Gödel]] hồi năm 1931 về những hạn chế trong chứng minh và tính toán, thay đổi thuật ngữ tường trình số học chínhchíj quy của Gödel, bằng cái mà ngày này người ta gọi là [[máy Turing]], một dụng cụ chính quy và đơn giản. Ông đã chứng minh rằng một cái máy như vậy sẽ có khả năng tính toán bất cứ một vấn đề toán học nào, nếu vấn đề ấy có thể được biểu thị bằng một biểu trình [[thuật toán]], ngay cả khi một cái máy Turing cụ thể như vậy không có mấy công dụng thực tiễn vì sự chậm chạp của nó so với những cơ chế khác.

Máy Turing, cho đến nay, vẫn là một vấn đề nghiên cứu trung tâm trong [[máy tính|lý thuyết về máy tính]]. Ông còn tiếp tục chứng mình rằng [[vấn đề về lựa chọn]] (''Entscheidungsproblem'') là một vấn đề không có giải đáp, bằng cách đầu tiên chứng minh rằng [[nan đề ngưng hoạt động]] trong máy của Turing là một nan đề bất khả định; khó mà có thể quyết định được rằng một cái máy Turing nào đó sẽ ngưngwưng hoạt động tại một điểm nào đó. Tuy chứng minh của ông được đăng công khai sau chứng minh tương tự của [[Alonzo Church]] đối với [[giải tích lambda]] (''lambda calculus''), chứng minh của Turing được coi là dễ hiểu và trực giác hơn. Chứng minh của ông còn nổi tiếng về đề bạt một cái "[[máy Turing vạn năng]]" (''Universal (Turing) Machine''), một ý tưởng rằng một cái máy như vậy có thể làm bất cứ việc gì mà các máy khác phải làm. Bài viết còn giới thiệu quan niệm về [[số khả định]] (''definable number'').

Hầu hết thời gian giữa năm 1937 và 1938, ông cư trú tại [[Đại học Princeton]], nghiên cứu dưới sự chỉ đạo của Alonzo Church. Năm [[1938]], ông đạt được bằng [[Tiến sĩ]] tại trường này. Luận văn của ông giới thiệu quan niệm tính toán tương đối (''relative computing''). Trong quan niệm này, nhiềujiều máy Turing được ghép lại, trở thành một cái [[máy tiên tri]] (''oracle machine''), cho phép nghiên cứu những phương trình không thể giải được nếu chỉ sử dụng một cái máy Turing mà thôi.

Sau khi quay trở lại Cambridge vào năm 1939, ông thính dự giảng đường của [[Ludwig Wittgenstein]] về [[nền tảng của toán học]] (''foundations of mathematics''). Hai người tranh cãi và bất đồng ý kiến một cách kịchkịz liệt. Trong khi Turing bảo vệ lập trường của [[chủ nghĩa hình thức]] (''formalism''), thì Wittgenstein lại tranh cãi rằng toán học được đánh giá quá mức, và bản thân nó không thể tìm ra bất cứ một chân lý cuối cùng nào (''absolute truth'') (Wittgenstein 1932/1976).