_icon.png
){kind=icon}
_wordmark.png)
用户:LynChern/Sandbox：修订间差异
更多操作
无编辑摘要 |
无编辑摘要 |
||
| 第123行： | 第123行： | ||
<references /> | <references /> | ||
[[Category:Concepts|概念]] | [[:Category:Concepts|概念]] | ||
2026年4月12日 (日) 00:59的版本
当心图灵焦油坑，其中一切皆有可能，但无趣之事皆不易。~ A. Perlis, 1982[1]
一个图灵焦油坑（Turing tarpit）是一种在具有最少功能的机器上构建的图灵完备语言。图灵焦油坑的创造与研究是计算机科学中最古老的主题之一。
历史
图灵焦油坑曾是计算机科学家最初的研究对象。两个最古老的焦油坑是阿隆佐·邱奇于1932年记录并在1936年发表的一个计算演算片段，以及他的学生艾伦·图灵于1936年发表的一个理论机器上的程序；如今，它们分别被称为λ演算和图灵机。邱奇和图灵证明了几个通用性和完备性结果，同时也验证了某些问题，特别是停机问题，是不可计算的观点。同样已知的是，组合子逻辑中的SKI基（由摩西·舍恩芬克尔于1920年发现并于1924年发表）可以编码λ演算，因此继承了图灵完备性的概念。
在接下来的十年里，随着可计算性理论的蓬勃发展，人们发现了更多的焦油坑，特别是埃米尔·波斯特于1946年提出的波斯特机。
1950年代，随着UNIVAC I交付给美国人口普查局，计算变得商业化，情况发生了变化。UNIVAC项目成员之一，格蕾丝·霍珀，推动为商业程序员开发易读的编程环境。这一推动导致了语法分析器和编译器理论的发展，以及计算机科学研究核心从可计算性理论整体上的转移。从1955年到1959年，霍珀领导一个团队创建了FLOW-MATIC，它后来直接影响了COBOL。从1961年Itiroo Sakai开始，CYK算法的变体被用于解析上下文无关语言。1966年，科拉多·博姆和朱塞佩·雅各皮尼证明了结构化程序定理，确立了流程图语言作为讨论算法的可读基础。总体而言，从1949年到1959年，计算从编写程序转变为编写计算机可读的解释性文档，在整个1960年代，解析和编译文档的理论基础是研究的主要焦点。
尽管如此，在整个1950年代和1960年代早期，学术界对图灵焦油坑仍有浓厚的兴趣，特别是在可计算性理论家中。1961年，王浩对王氏瓷砖提出了几个猜想，1966年罗伯特·伯杰通过证明一组二维王氏瓷砖是否能铺满平面是图灵完备的来回应。1964年，马文·明斯基证明了波斯特标记系统具有通用行为，满足了波斯特1943年的一个猜想。同样在1964年，博姆发表了P′′，这是Brainfuck的精神前身。
然而，到了1960年代中期，围绕它们的乐观泡沫破裂了。在其1987年的论文《The Busy Beaver Game and the Meaning of Life》中，艾伦·布雷迪讲述了大约1964年与约翰·麦卡锡（LISP的发明者）的一次私人谈话，麦卡锡教授在其中表示：
- 我们认为如果能找到最小的通用机器，那么我们就能学到很多关于可计算性的知识——当然事实并非如此！[2]
在其1967年著作《Computation: Finite and Infinite Machines》的最后一章《Very Simple Bases for Computability》中，马文·明斯基写道：
- 欢迎读者参与这场竞赛[设计最小的通用图灵机……]，但读者应该清楚地理解，这个问题是一个极其棘手的难题，本质上没有严肃的数学意义。
到了1980年代，图灵机被认为是与主流计算机科学不同的研究主题。在同一年，也就是1982年，艾伦·佩利斯创造了“图灵焦油坑”这个短语，并评论道：
尽管对它们的热情已经减退，但图灵焦油坑作为学术工具仍然有价值。它们在教学上可用于说明可计算性理论和编程语言原理的各个方面；例如，博姆关于结构化编程的见解正是他们研究图灵机的直接成果（Berendregt 2018）。[3] 它们还在算法信息论中有应用，因为简单的机器更容易分析。
然而，在深奥编程语言社区中对图灵焦油坑的追求，似乎本质上是为了追求本身。无论实践者是将这种追求视为一种消遣、一种艺术形式、非正式的研究，还是完全不同的东西——似乎可以肯定地说，他们一定很享受明斯基所指的“极其棘手的难题”。
语言要素
为了找到任意简单的机器，必须定义“简单性”——即需要最小化的某种度量标准。这个标准必须基于语言的一些可测量属性，通常归结为计算机器描述中某些语言要素的数量。有几种语言要素可供选择，它们之间的界限并不总是清晰的，这使定义成为一个挑战。
对于通用图灵机，常常使用状态数和符号数的乘积。克劳德·香农表明，状态数或符号数都可以减少到2——但代价是增加另一个的数量。明斯基和博布罗（通过穷举法）表明，没有仅包含2个状态且2个符号的图灵机是通用的。
然而，在编程语言中，状态并不总是容易或自然地度量，对于命令式语言，可以使用指令。函数式和重写语言可能会计算规约次数。我们可以使用（稍微模糊的）术语“操作”来指代这些中的任何一个，但应该理解，这些通常是不可比较的度量。
最小组合子基
- 主条目：组合子逻辑
组合子逻辑的原始问题之一是完整的组合子基可以有多小。我们可能考虑的第一个度量标准是基数，即基中有多少个组合子。一些小的完整基包括包含四个组合子的BCKW和包含两个组合子的SK。
能否存在单组合子基？也许可能，但它受相当严格的条件限制。考虑：
定理。 没有组合子是仿射且复制的。
定理。 如果一个基的每个组合子都是仿射的，那么它的系统不包含任何复制性组合子。
定理。 如果一个基没有消去性组合子，那么它的系统不包含K。
定理（最小秩）。 一个完整基必须至少有一个秩为三或以上的组合子。（Legrand 1988）[4][5]
因此，一个单组合子基将具有一个秩为三或以上的组合子，该组合子多次使用其某些参数，并且也丢弃某些参数。
最小闭λ项
- 主条目：闭λ项
福克尔给出了一个衡量单组合子简单性的度量标准；组合子的福克尔大小是它包含的抽象和应用的数量。一些具有小福克尔大小，并且能够在β归约下生成任何其他闭λ项的闭λ项包括：
- 梅雷迪思1963年的基[6] (74)
- 博姆的基 (23)
- 巴伦德雷赫特1971年的基 (18)
- 罗瑟的基 (14)
- 福克尔1992年的基[7] (12)
- Iota (11)
- 特朗普的Alpha (7)
单指令和零指令机器
任何机器都可以被视为只具有单一行为。从这个意义上说，有一种机械的方法可以将机器重新解释为只有一条指令，使得每个动作都由该机器的一行特定参数表示。这种构造被称为单指令集计算机或OISC。此外，还有一种机械的方法可以将参数重新解释为统一工作存储器中的位置，使得参数为零，并且每个动作都由机器的单一行为表示。这种构造被称为零指令集计算机或ZISC。
一些单指令图灵完备机器的例子，以及每条指令的参数数量包括：
- Subleq 减，若小于或等于零则跳转 (3)
- FlipJump 翻转并跳转 (2)
- Mov 移动 (2)
- I/D machine 递增并解引用 (1)
- RSSB 反向减并借位则跳过 (1)
零指令机器的例子包括像Black和Game of Life这样的元胞自动机。
调查
以下是一些大体上属于深奥编程语言的图灵焦油坑的粗略度量：
- +-)：3条指令，3个符号
- ///：3种实际指令类型，无限多个符号（图灵完备性只需要2个符号）
- 123：3个操作，3个符号
- Autopsy：2条指令，2个符号
- Binary combinatory logic：2个操作，2个符号
- BitChanger：4条指令，4个符号
- Bitwise Cyclic Tag：2条指令，2个符号
- Brainfuck：8条指令，8个符号
- Countable：5条指令（无I/O则为3条），7个符号（无I/O则为5个）
- iag：3条指令，>3个操作，3个符号
- Jot：3个操作，2个符号
- LAST：4条指令，4个符号，或对于LAST-B（二进制表示）为2个符号
- load：4条指令，4个符号
- P''：4条指令，4个符号
- Quinary Bueue：4条指令，4个符号
- QX：2条指令，2个符号（如果无穷大是有效常数，则为3个）
- SHITS：5条指令（无I/O则为3条），5个（无I/O则为3个）符号
- Tarski：6个操作，6个符号
- Thue：1个操作，4或5个符号（最小值）
- Ultimate bf instruction minimalization!：2个操作，2个符号
- Wierd：6个操作，2个符号
- X strike：4条指令，3个符号
另见
参考文献
- ↑ 1.0 1.1 A. Perlis, 1982, in SIGPLAN (September 1982). Epigrams in Programming. https://www.cs.yale.edu/homes/perlis-alan/quotes.html
- ↑ Brady, A. H. 1987. The Busy Beaver Game and the Meaning of Life. The Universal Turing Machine: A Half-Century Survey. pp 237-254. R. Herken, Ed. Springer-Verlag, NY. (ISBN 3-211-82637-8; ISBN 3-211-82628-9)
- ↑ H. P. Berendregt, 2018. Gems of Corrado Böhm. https://arxiv.org/abs/1812.02243
- ↑ R. Legrand, “A basis result in combinatory logic,” The Journal of Symbolic Logic, vol. 53, no. 4, pp. 1224–1226, 1988. doi:10.2307/2274616
- ↑ J. Tromp, P. L. Lumsdaine, 2022. Do combinatory logic bases need a function of 3 variables? https://mathoverflow.net/q/415373
- ↑ Carew A. Meredith. Single axioms for the systems (C, N), (C, O) and (A, N) of the two-valued propositional calculus. The journal of computing systems, vol. 1 no. 3 (1953), pp. 155–164. doi:10.2307/2268913
- ↑ Jeroen Fokker. 1992. The systematic construction of a one-combinator basis for Lambda-Terms. Form. Asp. Comput. 4, Suppl 1 (Nov 1992), 776–780. https://doi.org/10.1007/BF03180572