不确定性的困惑与NP理论分享 http://blog.sciencenet.cn/u/liuyu2205 平常心是道

博文

“停机问题”溯源 (Salvador Lucas)

已有 1020 次阅读 2024-11-7 18:24 |个人分类:图灵论著专研与精译工作群|系统分类:科研笔记

“The origins of the halting problem”的作者Salvador Lucas是西班牙的瓦伦西亚理工大学 (Universitat Politècnica de València) 计算机系的教授,在此文中作者详细探讨了停机问题的起源,指出停机问题既不是图灵在1936论文中提出的,也不是图灵关心的议题。然而,学术界的标准故事却把停机问题强加在图灵1936年这篇具有里程碑意义论文上,。。。

停机问题溯源

摘要

停机问题是不可判定问题的一个突出例子,它的提出和不可判定性证明通常归功于图灵 1936 发表的里程碑式的论文。不过, 科普兰(Copeland 2004 年注意到,这个问题的命名,显然是在马丁-维斯(Martin Davis1958 年的一本书中首次提出的。我们还提供了以下支持这一说法的部分论据: (i)图灵关注的是具有无限多位数的可计算(实数)数(如π),在他的论文中,图灵并不关注停机机器;(ii)图灵考虑的两个判定问题涉及他的机器产生特定类型输出的能力,而不是达到停机状态,图灵的计算概念中缺少这一点;(iii) 1936 年到 1958 年,在考虑该领域的文献时,没有一篇论文提到图灵机的任何停机问题,直到戴维斯的书。不过,(iv) 丘奇(Church)和(v) 克莱因(Kleene)做出了重要的初步贡献,对丘奇来说,终止是他的计算概念(λ-计算)的一部分,而克莱因(Kleene)在其 1952 年的著作中基本上提出了我们现在所知的停机问题。

The origins of the halting problem

Abstract

The halting problem is a prominent example of undecidable problem and its formulation and undecidability proof is usually attributed to Turing's 1936 landmark paper. Copeland noticed in 2004, though, that it was so named and, apparently, first stated in a 1958 book by Martin Davis. We provide additional arguments partially supporting this claim as follows: (i) with a focus on computable (real) numbers with infinitely many digits (e.g., π), in his paper Turing was not concerned with halting machines; (ii) the two decision problems considered by Turing concern the ability of his machines to produce specific kinds of outputs, rather than reaching a halting state, something which was missing from Turing's notion of computation; and (iii) from 1936 to 1958, when considering the literature of the field no paper refers to any “halting problem” of Turing Machines until Davis' book. However, there were important preliminary contributions by (iv) Church, for whom termination was part of his notion of computation (for the λ-calculus), and (v) Kleene, who essentially formulated, in his 1952 book, what we know as the halting problem now.

参考文献:

Salvador Lucas, The origins of the halting problem,

https://www.sciencedirect.com/science/article/pii/S235222082100050X



https://blog.sciencenet.cn/blog-2322490-1459061.html

上一篇:附录:关于东西方洞察整体的形式的讨论概要
下一篇:图灵与“停机问题”(Charles Petzold)
收藏 IP: 77.201.68.*| 热度|

2 郑永军 杨正瓴

该博文允许注册用户评论 请点击登录 评论 (5 个评论)

数据加载中...
扫一扫,分享此博文

Archiver|手机版|科学网 ( 京ICP备07017567号-12 )

GMT+8, 2024-12-7 22:48

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部