打开/关闭搜索
打开/关闭菜单
65
32
5
2690
LNN的:not(博客)？
打开/关闭外观设置菜单
打开/关闭个人菜单
未登录
未登录用户的IP地址会在进行任意编辑后公开展示。

用户:LynChern/Sandbox：修订间差异

来自 LNN的:not(博客)？
更多操作
←上一编辑下一编辑→
LynChern​（留言 | 贡献）
20次编辑
LynChern​（留言 | 贡献）
20次编辑
无编辑摘要
LynChern​（留言 | 贡献）
20次编辑
无编辑摘要
第1行： 第1行：
一个'''有限状态自动机'''，缩写为FSA，是一种简单的假想机器形式。它有时也被称为''有限状态机''、''有限自动机''或''有限状态转换器''。
<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|图灵完备]]语言。图灵焦油坑的创造与研究是计算机科学中最古老的主题之一。


（注意：FSA被用于各种目的——识别形式语言、建模系统的动态行为、在视频游戏中表示实体等——这些应用通常使用适合其问题域的略微不同的定义。我们将尝试在本页使用一个非常通用的定义，然后描述常见的变体。）
==历史==
 
图灵焦油坑曾是计算机科学家最初的研究对象。两个最古老的焦油坑是[[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年，艾伦·佩利斯创造了“图灵焦油坑”这个短语，并评论道：


在任何给定时间，FSA可以处于有限数量的''状态''中的任何一个。它从一个外部源逐个接收''输入信号''。当每个信号被接收时，FSA根据输入信号和FSA的当前状态''转换''到另一个（可能是相同的）状态。当没有更多的输入信号需要处理时，FSA可以被认为是留在一个''最终状态''。
:图灵机和现代计算机的区别是什么？这就像是[[wikipedia:Edmund Hillary|埃德蒙·希拉里]]攀登珠穆朗玛峰和在峰顶建立[[wikipedia:Conrad Hilton|希尔顿]]酒店之间的区别。<ref name="perlis" />


FSA也可能被认为产生''输出信号''，这些信号指向某个外部接收器。它可能在特定转换发生时（如在Mealy机中）或当达到特定状态时（如在Moore机中）产生这些信号。（这两种情况是等价的，除了所需的状态数量。）输出信号可能与输入信号性质相同或不同。
尽管对它们的热情已经减退，但图灵焦油坑作为学术工具仍然有价值。它们在教学上可用于说明可计算性理论和编程语言原理的各个方面；例如，博姆关于结构化编程的见解正是他们研究图灵机的直接成果（Berendregt 2018）。<ref>H. P. Berendregt, 2018. Gems of Corrado Böhm. https://arxiv.org/abs/1812.02243</ref> 它们还在[[wikipedia:algorithmic information theory|算法信息论]]中有应用，因为简单的机器更容易分析。


FSA可以被认为能够在每次转换或状态中产生多个输出信号。或者，一些转换可能根本不依赖于输入信号，自动移动到新状态。（这两种情况也是等价的，除了所需的状态数量。）
然而，在[[esoteric programming language|深奥编程语言]]社区中对图灵焦油坑的追求，似乎本质上是为了追求本身。无论实践者是将这种追求视为一种消遣、一种艺术形式、非正式的研究，还是完全不同的东西——似乎可以肯定地说，他们一定很享受明斯基所指的“极其棘手的难题”。


所有状态对于所有可能的输入信号都有一个转换。如果一个输入信号被认为是“非法的”，它不能被拒绝——FSA仍然必须转换到某个状态。这通常通过一个''非接受状态''来处理，该状态通过“非法”输入信号从所有状态转换到，并且FSA永远无法“逃脱”该状态。这个状态通常在图中被省略，只是隐含的。
==语言要素==


FSA的行为可以是确定性的或非确定性的；一个非确定性FSA可以同时处于多个状态；如果存在''某些''选择路径导致接受状态，它就接受一个输入。对于识别器，有一个算法可以移除非确定性，但通常会大大增加状态数量（最多2<sup>''n''</sup>，其中''n''是非确定性自动机中的状态数）。
为了找到任意简单的机器，必须定义“简单性”——即需要最小化的某种度量标准。这个标准必须基于语言的一些可测量属性，通常归结为计算机器描述中某些语言要素的数量。有几种语言要素可供选择，它们之间的界限并不总是清晰的，这使定义成为一个挑战。


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


FSA可以描绘为转换表，或更直观地，作为有向图，其中顶点是状态，边是状态之间的转换。边用转换发生的输入信号标注。输出信号可以在边、顶点或两者上标注。
然而，在编程语言中，状态并不总是容易或自然地度量，对于命令式语言，可以使用指令。函数式和重写语言可能会计算规约次数。我们可以使用（稍微模糊的）术语“操作”来指代这些中的任何一个，但应该理解，这些通常是''不可比较''的度量。


==语言识别==
== 最小组合子基 ==


为了识别一个字符串是否属于形式语言的一部分，例如[[regular expression|正则表达式]]，信号是字符串的符号，最终状态决定FSA是否“接受”该字符串——即，与FSA关联的形式语言是否包含该字符串。这种FSA通常不产生输出，而仅仅结束于“接受”或“拒绝”状态，被称为'''接受器'''或'''识别器'''。
:''主条目：[[Combinatory logic|组合子逻辑]]''


FSA足够强大以识别某些字符串集合，但不足以识别其他。例如，可以构造一个FSA，它能告诉你一个字符串是否以开括号开头并以闭括号结尾，无论该字符串有多长。然而，没有FSA能告诉你这些括号是否正确嵌套（正则表达式也不能）——为此，你需要一个[[push-down automaton|下推自动机]]。
组合子逻辑的原始问题之一是完整的组合子基可以有多小。我们可能考虑的第一个度量标准是'''基数'''，即基中有多少个组合子。一些小的完整基包括包含四个组合子的BCKW和包含两个组合子的SK。


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


FSA拥有较小但不容忽视的计算能力——如上所述，足以识别正则表达式。例如，它可以相加两个无界范围的整数。
'''定理。''' 没有组合子是仿射且复制的。


许多更强大的计算模型在施加微小限制后，结果在计算上等价于FSA。例如，一个只能向右移动的[[Turing machine|图灵机]]在计算上等价于FSA。
'''定理。''' 如果一个基的每个组合子都是仿射的，那么它的系统不包含任何复制性组合子。


许多[[esoteric programming language|深奥编程语言]]属于与FSA相同的[[computational class|计算类别]]。
'''定理。''' 如果一个基没有消去性组合子，那么它的系统不包含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个符号


以下引用来自Rabin和Scott[1959, "有限自动机及其决策问题," IBM Journal of Research and Development 3,2 (April, 1959), 114]：
==另见==


:"图灵机被广泛认为是数字计算机的抽象原型；然而，该领域的工作者越来越感到图灵机的概念过于笼统，无法作为实际计算机的精确模型。众所周知，即使对于简单计算，也不可能为图灵机在任何给定计算中所需的磁带量给出先验上界。正是这一特征使得图灵的概念不现实。"
* [[BF instruction minimalization|BF指令最小化]]，用于研究[[Brainfuck|Brainfuck]]的最小变体
* [[:Category:Turing tarpits|类别:图灵焦油坑]]，本维基上研究的
* [[Turning tarpit|Turning焦油坑]]，该概念的一个变体
* [[Unary]]，用于[[Brainfuck|Brainfuck]]的病态最小编码


:"在过去几年中，有限自动机的概念出现在文献中。这些机器只有有限数量的内部状态，可用于存储和计算。有限性的限制似乎能更好地近似物理机器的概念。当然，这种机器不能像图灵机那样做那么多，但能够计算任意一般递归函数的优势是值得怀疑的，因为这些函数在实际应用中很少出现。"
== 参考文献 ==
<references />


[[Category: Computational models|计算模型]]
[[Category:Concepts|概念]]

2026年4月12日 (日) 00:58的版本

当心图灵焦油坑，其中一切皆有可能，但无趣之事皆不易。~ 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年，艾伦·佩利斯创造了“图灵焦油坑”这个短语，并评论道：

图灵机和现代计算机的区别是什么？这就像是埃德蒙·希拉里攀登珠穆朗玛峰和在峰顶建立希尔顿酒店之间的区别。[1]

尽管对它们的热情已经减退，但图灵焦油坑作为学术工具仍然有价值。它们在教学上可用于说明可计算性理论和编程语言原理的各个方面；例如，博姆关于结构化编程的见解正是他们研究图灵机的直接成果（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

任何机器都可以被视为只具有单一行为。从这个意义上说，有一种机械的方法可以将机器重新解释为只有一条指令，使得每个动作都由该机器的一行特定参数表示。这种构造被称为单指令集计算机或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. ↑ 1.0 1.1 A. Perlis, 1982, in SIGPLAN (September 1982). Epigrams in Programming. https://www.cs.yale.edu/homes/perlis-alan/quotes.html
  2. ↑ 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)
  3. ↑ H. P. Berendregt, 2018. Gems of Corrado Böhm. https://arxiv.org/abs/1812.02243
  4. ↑ 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
  5. ↑ J. Tromp, P. L. Lumsdaine, 2022. Do combinatory logic bases need a function of 3 variables? https://mathoverflow.net/q/415373
  6. ↑ 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
  7. ↑ 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
检索自“https://notblog.vudrux.site/index.php?title=用户:LynChern/Sandbox&oldid=2917”
最后修改时间
此页面最后编辑于2026年4月12日 (星期日) 00:58。