查看“︁用户:LynChern/Sandbox”︁的源代码

<blockquote>
当心图灵焦油坑，其中一切皆有可能，但无趣之事皆不易。~ A. Perlis, 1982<ref name="perlis">A. Perlis, 1982, in SIGPLAN (September 1982). Epigrams in Programming. https://www.cs.yale.edu/homes/perlis-alan/quotes.html</ref>
</blockquote>

一个'''图灵焦油坑'''（Turing tarpit）是一种在具有最少功能的机器上构建的[[Turing-complete|图灵完备]]语言。图灵焦油坑的创造与研究是计算机科学中最古老的主题之一。

==历史==

图灵焦油坑曾是计算机科学家最初的研究对象。两个最古老的焦油坑是[[Alonzo Church|阿隆佐·邱奇]]于1932年记录并在1936年发表的一个计算演算片段，以及他的学生[[Alan Turing|艾伦·图灵]]于1936年发表的一个理论机器上的程序；如今，它们分别被称为[[lambda calculus|λ演算]]和[[Turing machine|图灵机]]。邱奇和图灵证明了几个通用性和完备性结果，同时也验证了某些问题，特别是[[halting problem|停机问题]]，是不可计算的观点。同样已知的是，[[combinatory logic|组合子逻辑]]中的SKI基（由[[Moses Schönfinkel|摩西·舍恩芬克尔]]于1920年发现并于1924年发表）可以编码λ演算，因此继承了[[Turing-completeness|图灵完备性]]的概念。

在接下来的十年里，随着可计算性理论的蓬勃发展，人们发现了更多的焦油坑，特别是[[Emil Post|埃米尔·波斯特]]于1946年提出的[[Post correspondence problem|波斯特机]]。

1950年代，随着[[wikipedia:UNIVAC I|UNIVAC I]]交付给美国人口普查局，计算变得商业化，情况发生了变化。UNIVAC项目成员之一，[[Grace Hopper|格蕾丝·霍珀]]，推动为商业程序员开发易读的编程环境。这一推动导致了语法分析器和编译器理论的发展，以及计算机科学研究核心从可计算性理论整体上的转移。从1955年到1959年，霍珀领导一个团队创建了[[FLOW-MATIC]]，它后来直接影响了[[COBOL]]。从1961年Itiroo Sakai开始，[[wikipedia:CYK algorithm|CYK算法]]的变体被用于解析上下文无关语言。1966年，[[Corrado Böhm|科拉多·博姆]]和[[Giuseppe Jacopini|朱塞佩·雅各皮尼]]证明了[[wikipedia:structured program theorem|结构化程序定理]]，确立了流程图语言作为讨论算法的可读基础。总体而言，从1949年到1959年，计算从编写程序转变为编写计算机可读的解释性文档，在整个1960年代，解析和编译文档的理论基础是研究的主要焦点。

尽管如此，在整个1950年代和1960年代早期，学术界对图灵焦油坑仍有浓厚的兴趣，特别是在可计算性理论家中。1961年，[[Hao Wang|王浩]]对[[Wang tile|王氏瓷砖]]提出了几个猜想，1966年[[Robert Berger|罗伯特·伯杰]]通过证明一组二维王氏瓷砖是否能铺满平面是图灵完备的来回应。1964年，[[Marvin Minsky|马文·明斯基]]证明了[[tag system|波斯特标记系统]]具有通用行为，满足了波斯特1943年的一个猜想。同样在1964年，博姆发表了[[P′′]]，这是[[Brainfuck|Brainfuck]]的精神前身。

然而，到了1960年代中期，围绕它们的乐观泡沫破裂了。在其1987年的论文《The Busy Beaver Game and the Meaning of Life》中，艾伦·布雷迪讲述了大约1964年与约翰·麦卡锡（LISP的发明者）的一次私人谈话，麦卡锡教授在其中表示：

:我们认为如果能找到最小的通用机器，那么我们就能学到很多关于可计算性的知识——当然事实并非如此！<ref>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)</ref>

在其1967年著作《Computation: Finite and Infinite Machines》的最后一章《Very Simple Bases for Computability》中，马文·明斯基写道：

:欢迎读者参与这场竞赛[设计最小的[[universal Turing machine|通用图灵机]]……]，但读者应该清楚地理解，这个问题是一个极其棘手的难题，本质上''没有''严肃的数学意义。

到了1980年代，图灵机被认为是与主流计算机科学不同的研究主题。在同一年，也就是1982年，艾伦·佩利斯创造了“图灵焦油坑”这个短语，并评论道：

:图灵机和现代计算机的区别是什么？这就像是[[wikipedia:Edmund Hillary|埃德蒙·希拉里]]攀登珠穆朗玛峰和在峰顶建立[[wikipedia:Conrad Hilton|希尔顿]]酒店之间的区别。<ref name="perlis" />

尽管对它们的热情已经减退，但图灵焦油坑作为学术工具仍然有价值。它们在教学上可用于说明可计算性理论和编程语言原理的各个方面；例如，博姆关于结构化编程的见解正是他们研究图灵机的直接成果（Berendregt 2018）。<ref>H. P. Berendregt, 2018. Gems of Corrado Böhm. https://arxiv.org/abs/1812.02243</ref> 它们还在[[wikipedia:algorithmic information theory|算法信息论]]中有应用，因为简单的机器更容易分析。

然而，在[[esoteric programming language|深奥编程语言]]社区中对图灵焦油坑的追求，似乎本质上是为了追求本身。无论实践者是将这种追求视为一种消遣、一种艺术形式、非正式的研究，还是完全不同的东西——似乎可以肯定地说，他们一定很享受明斯基所指的“极其棘手的难题”。

==语言要素==

为了找到任意简单的机器，必须定义“简单性”——即需要最小化的某种度量标准。这个标准必须基于语言的一些可测量属性，通常归结为计算机器描述中某些语言要素的数量。有几种语言要素可供选择，它们之间的界限并不总是清晰的，这使定义成为一个挑战。

对于通用图灵机，常常使用状态数和符号数的乘积。克劳德·香农表明，状态数''或''符号数都可以减少到2——但代价是增加另一个的数量。明斯基和博布罗（通过穷举法）表明，没有仅包含2个状态''且''2个符号的图灵机是通用的。

然而，在编程语言中，状态并不总是容易或自然地度量，对于命令式语言，可以使用指令。函数式和重写语言可能会计算规约次数。我们可以使用（稍微模糊的）术语“操作”来指代这些中的任何一个，但应该理解，这些通常是''不可比较''的度量。

== 最小组合子基 ==

:''主条目：[[Combinatory logic|组合子逻辑]]''

组合子逻辑的原始问题之一是完整的组合子基可以有多小。我们可能考虑的第一个度量标准是'''基数'''，即基中有多少个组合子。一些小的完整基包括包含四个组合子的BCKW和包含两个组合子的SK。

能否存在单组合子基？也许可能，但它受相当严格的条件限制。考虑：

'''定理。''' 没有组合子是仿射且复制的。

'''定理。''' 如果一个基的每个组合子都是仿射的，那么它的系统不包含任何复制性组合子。

'''定理。''' 如果一个基没有消去性组合子，那么它的系统不包含K。

'''定理（最小秩）。''' 一个完整基必须至少有一个秩为三或以上的组合子。（Legrand 1988）<ref>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</ref><ref>J. Tromp, P. L. Lumsdaine, 2022. Do combinatory logic bases need a function of 3 variables? https://mathoverflow.net/q/415373</ref>

因此，一个单组合子基将具有一个秩为三或以上的组合子，该组合子多次使用其某些参数，并且也丢弃某些参数。

== 最小闭λ项 ==

:''主条目：[[Closed lambda term|闭λ项]]''

福克尔给出了一个衡量单组合子简单性的度量标准；组合子的'''福克尔大小'''是它包含的抽象和应用的数量。一些具有小福克尔大小，并且能够在β归约下生成任何其他闭λ项的闭λ项包括：

* 梅雷迪思1963年的基<ref>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</ref> (74)
* 博姆的基 (23)
* 巴伦德雷赫特1971年的基 (18)
* 罗瑟的基 (14)
* 福克尔1992年的基<ref>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</ref> (12)
* [[Iota]] (11)
* 特朗普的Alpha (7)

== 单指令和零指令机器 ==

:''主条目：[[OISC]]， [[ZISC]]''

任何机器都可以被视为只具有单一行为。从这个意义上说，有一种机械的方法可以将机器重新解释为只有一条指令，使得每个动作都由该机器的一行特定参数表示。这种构造被称为'''单指令集计算机'''或'''OISC'''。此外，还有一种机械的方法可以将参数重新解释为统一工作存储器中的位置，使得参数为零，并且每个动作都由机器的单一行为表示。这种构造被称为'''零指令集计算机'''或'''ZISC'''。

一些单指令[[Turing-complete|图灵完备]]机器的例子，以及每条指令的参数数量包括：

* [[Subleq]] ''减，若小于或等于零则跳转'' (3)
* [[FlipJump]] ''翻转并跳转'' (2)
* [[Mov]] ''移动'' (2)
* [[I/D machine]] ''递增并解引用'' (1)
* [[RSSB]] ''反向减并借位则跳过'' (1)

零指令机器的例子包括像[[Black]]和[[Game of Life]]这样的[[cellular automaton|元胞自动机]]。

==调查==

以下是一些大体上属于[[esoteric programming language|深奥编程语言]]的图灵焦油坑的粗略度量：
* [[+-)]]：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个符号

==另见==

* [[BF instruction minimalization|BF指令最小化]]，用于研究[[Brainfuck|Brainfuck]]的最小变体
* [[:Category:Turing tarpits|类别:图灵焦油坑]]，本维基上研究的
* [[Turning tarpit|Turning焦油坑]]，该概念的一个变体
* [[Unary]]，用于[[Brainfuck|Brainfuck]]的病态最小编码

== 参考文献 ==
<references />

[[Category:Concepts|概念]]