{"resolved":true,"match_type":"uuid","source_type":"original_book","book_id":"ea3b7167-0435-4a94-84b9-80a5359326a4","title":"递归与偶然","author":null,"edition":null,"publisher":null,"year":null,"isbn":"9787576004694","requested_by":"printed_page","book":{"source_type":"original_book","book_id":"ea3b7167-0435-4a94-84b9-80a5359326a4","id":"ea3b7167-0435-4a94-84b9-80a5359326a4","uuid":"ea3b7167-0435-4a94-84b9-80a5359326a4","title":"递归与偶然","normalized_title":"递归与偶然","author":null,"edition":null,"publisher":null,"year":null,"isbn":"9787576004694","isbns":["9787576004694"],"parsed":true,"ai_readable":true,"document_type":"book","page_count":401,"navigation_url":"https://workshop.closeclaw.top/ai/book/ea3b7167-0435-4a94-84b9-80a5359326a4","title_url":"https://workshop.closeclaw.top/ai/title/%E9%80%92%E5%BD%92%E4%B8%8E%E5%81%B6%E7%84%B6","fixed_page_url_template":"https://workshop.closeclaw.top/ai/book/ea3b7167-0435-4a94-84b9-80a5359326a4/page/{printed_page}","path_api_url_template":"https://workshop.closeclaw.top/api/ai/book/ea3b7167-0435-4a94-84b9-80a5359326a4/page/{printed_page}","read_url":"https://workshop.closeclaw.top/api/ai/read/ea3b7167-0435-4a94-84b9-80a5359326a4","page_url":"https://workshop.closeclaw.top/api/ai/books/ea3b7167-0435-4a94-84b9-80a5359326a4/page","search_url":"https://workshop.closeclaw.top/api/ai/books/ea3b7167-0435-4a94-84b9-80a5359326a4/search"},"page":{"printed_page":141,"pdf_page":153,"physical_index":153,"physical_index_base":0,"printed_page_status":"recognized","page_sha256":"7ce6d1e73c9aa6b563c2712124ed1e51b1aa54bbd555a783e5347161696b58bc"},"chapter":"第二章逻辑与偶然","content":"[113]在哥德尔之后，图灵1936年的论文和斯蒂芬·克莱尼(Stephen Kleene，阿隆佐·邱奇[Alonzo Church]的学生)进一步定义了一般递归性——比如不动点定理(FixedPoint Theorem)②和正规形理论(Normal Form Theory)③;随后，邱奇在1937年对图灵1936年的论文《论可计算数及其在判定问题上的应用》(On Computable Numbers，with an Ap-plication to the Entscheidungsproblem)的评论中表示，埃尔布朗—哥德尔一克莱尼的一般递归函数等价于图灵的通用机，以及邱奇的 λ可定义函数(Lambda definable function)。①我们或许可以说，对图灵而言，可计算或可判定的东西总是递归可枚举的，即使有些计算机科学家(如罗伯特·索阿雷)建议用可判定性和可计算性的说法代替递归性，②因为递归一词在日常使用中有多种含义。然而，这种做法会忽略递归形式—它在数学和哲学理解中发挥核心作用—的重要性。一个递归函数可能无法实现其目标，因此不能停机。在这种情况下它会在无限循环中迷失，直至耗尽计算资源，比如耗尽内存，甚至达到机器的物理疲劳上限。而通用图灵机试图规定的正是这种不可判定性，以避免这种无限循环。\n\n第二章逻辑与偶然\n\n141\n\n① 皮埃尔·利维，《递归的概念，从控制论到联结主义》(Lanotion de récursivité, de la première cybernétique au connexionnisme), 见 Intellectica39,2004年2月，第126页。\n\n② 这个理论可以简单表述为：对于每一个图灵可计算的总函数f(x),都有一个不动点 n,使 φf(n)=φn(后面我们将看到不动点的说法再次出现，如终止状态[terminal state])。\n\n③在此我们可以借用索阿雷的总结：存在一个原始递归谓词T(e,x,y)和一个原始递归函数∪(y),对于任何一般递归函数φ(x),都有一个索引 e,使 φ(x)=U(μy T(e, x, y))。见罗伯特·索阿雷(Robert I.Soare)，《可计算性和递归》(Computability and Recursion)，见《符号逻辑简报》(Bulletin o f Symbolic Logic),2,第 3期，1996年，第 301页。","previous_page":140,"next_page":142}