Wikipedia

Khác biệt giữa bản sửa đổi của “Lý thuyết tính toán”

Duyệt lịch sử tương tác
← Thay đổi trướcThay đổi sau →
Nội dung được xóa Nội dung được thêm vào
Trực quanMã wiki
n replaced: . → . (5), . <ref → .<ref, removed: Thể loại:Pages with unreviewed translations using AWB
Dòng 9:
 
== Tập hợp tính toán được và không tính toán được ==
Lý thuyết đệ quy bắt nguồn từ những năm 1930, với công trình của [[Kurt Gödel]], [[Nhà thờ Alonzo|Alonzo Church]], [[Rózsa Péter]], [[Alan Turing]], [[Stephen Kleene]] và [[Bài viết của Emil|Emil Post]].<ref>Many of these foundational papers are collected in ''The Undecidable'' (1965) edited by [[Martin Davis (mathematician)|Martin Davis]].</ref><ref>{{Chú thích web|url=http://www.people.cs.uchicago.edu/~soare/Turing/frontice.pdf|title=Computability Theory and Applications: The Art of Classical Computability|author=Soare|first=Robert Irving|date=ngày 22 Decembertháng 12 năm 2011|website=Department of Mathematics|publisher=University of Chicago|access-dateaccessdate =ngày 23 Augusttháng 8 năm 2017}}</ref>
 
Các kết quả cơ bản mà các nhà nghiên cứu thu được đã thiết lập [[Hàm tính toán được|tính toán Turing]] như là sự chính thức hóa chính xác của ý tưởng không chính thức về tính toán hiệu quả. Những kết quả này đã khiến [[Stephen Kleene]] (1952) đặt ra hai tên "Luận án của Church" (Kleene 1952: 300) và "Luận án của Turing" (Kleene 1952: 376). Ngày nay, những điều này thường được coi là một giả thuyết duy nhất, '''[[luận án Church-Turing]]''', nói rằng bất kỳ hàm nào có thể tính toán được bằng [[thuật toán]] là một [[hàm tính toán được]]. Mặc dù ban đầu còn hoài nghi, đến năm 1946, Gôdel đã lập luận ủng hộ luận điểm này:
Lấy từ “https://vi.wikipedia.org/wiki/Lý_thuyết_tính_toán”