看似不可能的函数式程序

Andrej邀请我写一些令人惊讶的函数程序。第一个程序，由于Ulrich Berger(1990)，对无限二进制位序列的“康托空间”进行了详尽的研究。我在结尾处包括了参考资料。弱形式的穷举搜索相当于检查对Cantor空间的所有元素是否都有一个全谓词。因此，这相当于康托空间上的普遍量子化。这有可能在有限的时间内通过算法完成吗？

一个更有力的例子相当于找到一个例子，如果存在这样的例子，那么谓词是成立的，并且说没有其他的例子。

我将使用Haskell语言，但可以快速将程序转换为ML或OCaml。这里显示的源代码是作为看似不可能的.hs附加的。

我们可以使用布尔值来表示二进制数字，甚至整数，但我更喜欢使用不同的类型来避免混淆：

Deriving子句告诉Haskell找出如何自动确定位相等。

对于无限序列的类型，我们可以对这里讨论的大多数算法使用内置类型的flazy列表。但是，为了说明某些观点，我将从数学的角度，把序列看作是定义在自然数上的函数。Haskell定义的下一个版本将具有内置的自然数类型。目前，我将其实现为integer类型：

运算符(#)取一个位x和一个序列a，并生成一个新序列x#a，其中x为头，a为尾(非常类似于列表的内置运算(：))：

>；(#)：：bit->；Cantor->；Cantor>；x#a=\i->；如果i==0，则x否则为a(i-1)

接下来，我们来看问题的核心，在康托空间上进行穷尽搜索的功能。函数find的规定是，对于任何总数p，都应该使find p总是坎托空间的一个全元素，而且，如果在Cantor空间中有a且p=True，则a=find p就是这种a的一个例子。

>；某些，永远：：(Cantor->；Bool)->；Bool>；Find：：(Cantor->；Bool)->；Cantor。

因为我将有几个find实现，所以我必须选择一个才能编译和运行程序。神职人员的选择是第一个，

但是你会被邀请去做其他的实验。要使下面的find_i定义有意义，您必须选择上面的选择。

函数find在CATORSPACE上接受一个谓词，因此它通常有一个$\lambda$-表达式作为参数。在下面的定义中，这不是必需的，因为根据$\eta$规则，(\a->；pa)=p。但为了清楚起见，我采用了它，因为这样我们就可以大声地将“find(\a->；pa)”理解为“find a so to p(A)”：

>；for ome p=p(find(\a->；pa))>；forevery p=not(for ome(\a->；not(Pa)。

请注意，函数Forevery(全称量化)是通过德摩根定律从函数For Some(存在量化)获得的。某些和find_i的泛函由相互递归定义：

>；find_i：：(Cantor-gt；Bool)->；Cantor>；find_i p=if for ome(\a->；p(零#a))>；则为零#find_i(\a->；p(零#a))>；否则一个#find_i(\a->；p(一#a))

算法find_i的直观思想很清楚：如果有一个示例从零开始，那么结果就从零开始，否则就必须从一开始。然后我们用同样的想法紧急建造尾巴。可能不清楚的是，由于通过调用forome进行间接递归调用，递归最终是否会产生一个数字。数学证明是通过归纳p的一致连续性模来进行的，定义如下。

更自然的做法是，只有在有示例的情况下才返回示例，否则就会说没有示例：

>；搜索：：(Cantor->；Bool)->；或许Cantor>；搜索p=如果查找一些(\a->；pa)，则只查找(find(\a->；pa))。

类型理论备注：类型可能对应于SUM类型$A+1$，其中$1$的唯一元素称为Nothing，而Just是插入$A\Toa+1$。

练习：显示forome和find都可以直接从搜索中定义，假设我们首先定义了搜索。

常识告诉我们，函数类型没有明显的相等。事实上，例如，众所周知，由于暂停问题，函数类型Integer->；Integer不具有可判定的等价性。然而，常识并不总是正确的，事实上，其他一些函数类型确实具有可判定的相等，例如，对于任何具有可判定相等的类型y，都有Cantor->；y类型，这与图灵没有矛盾：

>；等于：：eq y=>；(Cantor->；y)->；(Cantor->；y)->；Bool>；等于f g=永远(\a->；f a==g a)。

这似乎很奇怪，甚至有点可疑，因为在某种意义上，康托空间比整数还大。在接下来的帖子中，我将解释这与这样一个事实有关，即广空间在拓扑上是紧凑的，但是整数不是。

>；强制：：bit->；自然>；强制零=0>；强制一=1>；f，g，h：：Cantor->；整数>；fa=强制(a(7*强制(A4)+4*(强制(A7))+4))>；g a=强制(a(强制(A4)+11*(强制(A7)。则如果a 4==0，则强制(A 4)否则强制(A 11)；否则，如果a 4==1，则强制(A 15)否则强制(A 8)。

$GHCI似乎不可能。lhs_/_/__(_)//_/||GHC Interactive，版本6.6，适用于Haskell 98。//_/__//_||http://www.haskell.org/ghc/_///_/__/|_|类型：？寻求帮助。正在加载包裹基地.。正在链接.。完成。[第1页，共1页]编译Main(似乎不可能.lhs，解释)OK，模块已加载：Main.*Main>；

此时，我们可以在解释器的提示下计算表达式。首先，我要求它在每次计算后打印时间和空间使用情况：

*Main>；等于f gFalse(0.10秒，3490296字节)*Main>；等于f hTrue(0.87秒，36048844字节)*Main>；等于g hFalse(0.09秒，3494064字节)*Main>；等于f fTrue(0.91秒，38642544字节)*Main>；等于g gTrue(0.15秒，6127796字节)*Main>；等于h hTrue(0.83秒，32787372字节)。

通过改变find的实现，我将使其更快，也将能够运行更大的示例。但是，让我们暂时继续当前的实现。

>；模量：：(Cantor->；整数)->；自然>；模量f=最小(\n->；永远(\a->；永远(\b->；eq n a b->；(f a==f b)。

这有时被称为Fan泛函，可以追溯到Brouwer(20世纪20年代)，它在更高类型的可计算性理论社区中是众所周知的(参见下面的Normann(2006))。它求出定义为最小自然数$n$的一致连续模，使得。

这里所说的是，可计算泛函是连续的，也就是说，有限数量的输出只依赖于有限数量的输入。但康托空间是紧的，在分析和拓扑学中有一个定理说，定义在紧空间上的连续函数是一致连续的。在此上下文中，这相当于存在单个$n$，因此对于所有输入，只需查看深度$n$即可获得答案(在本例中，答案始终是有限的，因为它是整数)。我将在另一篇文章中解释这一切。在这里，我将通过运行一些示例中的程序来说明这一点。

请注意，如果我们定义了所有其他需要的成分，则Haskell定义与数学计算相同：

>；至少：：(Natural-gt；Bool)->；Natural>；至少p=if p 0则0否则1+最少(\n->；p(n+1))>；(-->；)：：Bool->；Bool->；Bool>；p-->；q=not p||q>；eq：：Natural->；Cantor-&。等式(n+1)a b=a n==b n&；&；eq n a b。

>；项目：：Natural->；(Cantor->；整数)>；项目i=\a->；强制(Ai)。

*主模(\a->；45000)0(0.00秒，0字节)*主模(投影1)2(0.00秒，0字节)*主模(投影2)3(0.01秒，0字节)*主模(投影3)4(0.05秒，820144字节)*主模(投影4)5(0.30秒，5173540字节)*主模(投影3)4(0.05秒，820144字节)*主模(投影4)5(0.30秒，5173540字节)*主模(投影3)4(0.05秒，0字节)*主模(投影4)5(0.30秒，5173540字节)*主模。模数(项目6)7(9.24秒，171456820字节)。

因此，直观地说，模数是函数使用的输入的最后一个指数加1。对于像上面这样的常量函数，模数是零，因为没有使用索引。

技术评论。证明FIND_i的终止性所需的一致连续模的概念不是字面上的相同，而是稍有不同(有时称为内涵一致连续模，而我们的称为外延一致连续模)。但我不会在这里讨论这种数学上的微妙之处。主要思想是，当模数为$0$时，循环终止，跟随find_i定义的一个分支，并开始新的递归，以产生示例的下一个数字。当p的模数为$n+1$时，谓词\a->；p(Zero#a)的模数为$n$或更小，因此递归调用总是以较小的模数进行，并因此最终终止。说完了。

现在，我将尝试获得更快的find实现。我将分几个阶段修改原始实现。首先，我将通过扩展函数find_i定义中的一些函数的定义来删除相互递归：

>；find_ii p=if p(零#find_ii(\a->；p(零#a)>；则零#find_ii(\a->；p(零#a))>；否则一个#find_ii(\a->；p(one#a))

这应该具有基本相同的速度。现在请注意，如果我们将0和1作为参数h，则条件的分支是相同的。因此，可以按如下方式对条件进行“因式分解”：

>；find_iii：：(Cantor->；Bool)->；Cantor>；find_III p=h#find_III(\a->；p(h#a))>；其中h=if p(Zero#find_III(\a->；p(Zero#a)，则为零。

这是(指数级的！)。在某些情况下，速度会更快。这方面的一个线索是，h只有在“使用”时才会被求值(我们的语言是懒惰的)。让我们运行一个示例，将上面的find定义替换为find=find_iii：

*Main>；等于f hTrue(0.00秒，522668字节)*Main>；等于(Proj1000)(Proj1000)True(0.00秒，0字节)*Main>；等于(Proj1000)(Proj4000)False(0.03秒，1422680字节)*Main>；等于(Proj1000)(Proj(2^20))False(7.02秒，336290704字节)。

如你所见，我们尝试的投影函数越大，比较的时间就越长。要查看第一个算法有多糟糕，让我们切换回find=find_i：

*Main>；等于(项目10)(项目10)TRUE(0.05秒，1529036字节)*Main>；等于(项目10)(项目15)FALSE(1.61秒，72659036字节)*Main>；等于(项目10)(项目20)FALSE(60.62秒，2780497676字节)。

前面的例子不能用这个算法运行，除非我们有比可观测宇宙中的原子更多的可用位，并且我们愿意等待数十亿年，因为这个算法在连续的模数上是指数的。

>；find_iv：：(Cantor->；Bool)->；Cantor>；find_iv p=let leftBranch=零#find_iv(\a->；p(零#a))>；in if p(LeftBranch)>；则左分支>；否则一个#find_iv(\a->；p(one#a))

实际上，我从来没有想过这个算法的性能，也没有用它做过实验。让我们看看我们得到了什么(您需要替换find=find_iv)：

*Main&>EQUAL(Proj10)(Proj20)False(0.00秒，522120字节)*Main&>EQUAL(Proj10)(Proj200)False(0.04秒，1550824字节)*Main&>EQUAL(Proj10)(Proj2000)False(3.71秒，146039744字节)*Main&>EQUAL(Proj10)(Proj20000)中断。

比Find_I好多了，但比Find_III差多了！我在上一个例子中放弃了，因为它在大约一分钟后开始放慢我编辑这篇帖子的速度。

但是有一个更好的算法，我现在提出。我不会试图在这篇文章中解释这个算法的工作原理(如果你真的感兴趣，请参阅下面的LICS 2007年的论文)，但我会在下面做几点说明：

>；find_v：：(Cantor->；Bool)->；Cantor>；find_v p=\n->；if q n(find_v(Q N))则为零其他一>；其中q n a=p(\i->；如果i<；n则find_v p i Else if i==n则为零其他a(i-n-1))。

上面所有的算法，除了这个，都可以很容易地重写，使用懒惰列表，而不是定义在自然数上的函数。该算法利用了这样一个事实，即要访问表示为函数的序列的元素，不必扫描所有前面的元素。这个算法以一种可能很神秘的方式，隐式地找出它的参数p使用了哪些条目，并且只显式地构造了那些条目。如果愿意，您可以访问其他类型，但是算法find_v不强制它们的求值。认为find_v是正确的一种方法是，通过对n的归纳，证明find_i p n=find_v p n，这并不太困难，尽管如果不仔细引入适当的辅助记法，在某些阶段的计算会变得很大。一种更好的方法是直接理解这一点，就像上面的文章中所做的那样(您需要寻找产品的功能性，它概括了这一点)。

*Main>；EQUAL(PROJ(2^300))(PROJ(2^300))TRUE(0.00秒，522148字节)*Main&>EQUAL(PROJ(2^300))(PROJ(2^400))FALSE(0.0秒，525064字节)。

但是，如果函数使用多个参数，而不是只使用一个参数(参见下面的示例)，这就不再那么好了。要解决此问题，请先按如下方式编写上述程序，引入辅助变量b来命名结果，并替换其中一个递归调用(有两个)以使用b：

>；find_vi：：(Cantor->；Bool)->；Cantor>；find_vi p=b>；其中b=\n->；If q n(find_vi(Q N))则另有一>；Q n a=p(\i->；If i<；n则b i Else if i==n则Zero Else a(i-n-1))。

懒惰求值在这里没有帮助，因为b是函数，实际上这会使程序稍微变慢。现在，为了显著提高速度，我们将标识函数应用于b的定义，或者更确切地说，是标识函数的一个精心实现，它以广度优先的方式将b存储到无限二叉树中，然后再将其检索回来(此技巧使用对数开销实现记忆)：

>；find_vii：：(Cantor->；Bool)->；Cantor>；find_vii p=b>；其中b=id&39；(\n->；if q n(find_vii(Qn))则为零其他一)>；q n a=p(\i->；if i<；n则b i Else if i==n则为零a(i-n-1)。code：：(Natural-gt；x)->；Tx>；code f=B(F0)(code(\n->；f(2*n+1))>；(code(\n->；f(2*n+2))>；decode：：t x->；(Natural->；x)>；decode(B X L R)n|n==0=x&x。|ELSE=解码r((n-2)`div`2)>；id'；：(Natural->；x)->；(Natural->；x)>；id'；=decde.code。

>；f'；，g'；，h'；：：Cantor->；整数&>f&39；a=a'；(10*a'；(3^80)+100*a'；(4^80)+1000*a'；(5^80))，其中a'；i=强制(Ai)>；g'；a=a'；(10*a'；(3^80)+100*a'；(4^80)+1000*a'；(6^80)其中a'；i=强制(Ai)&>；h&39；a=a'；k&>其中i=if a'；(5^80)==0则其他1000&>j=如果a'；(3^80)==1则10+i否则i&>k=如果a'；(4^80)==0则j否则100+j&>。False(6.75秒，814435692字节)*Main&>；等于f'；h'；True(3.20秒，383266912字节)*Main&>；等于g'；h'；False(6.79秒，813083216字节)*Main&>；等于f'；f'；True(3.20秒，383384908字节)*Main&>；等于g'；g'；True(3.31秒，400711084字节。TRUE(3.22秒，383274252字节)。

在所有上述算法中，只有FIND_VII能够处理上述示例。一个更有趣的例子是这个。自然数的两个有限序列$s$和$t$具有相同的元素集当且仅当两个函数。

相等，其中上述符号表示投影的点逻辑AND(合取)，其中$|s|$是$s$的长度。下面是thidea的一个实现：

>；点与：：[Natural]->；(Cantor-gt；Bool)>；点与[]=\b->；True>；点与(n：a)=\b->；(b n==一个)&；&；点与b>；相同元素：：[Natural]->；[Natural]->；Bool。相同元素[6^60，5^50，1，5，6，6，8，9，3，4，6，2，4，6，1，6^60，7^700，1，1，3，3^30][1，2，3，4，5，6，7，8，9，3^30，5^50，6^60，7^70]FALSE(0.14秒，21716248字节)*Main>；相同元素[6^60，5^50，1，5，6，6，8，9，3，4，6，2，4，6，1，6^60，7^70，1，1，1，3，3^30][1，2，3，4，5，6，7，8，9，3^30，5^50，6^60，7^70]FALSE(0.10秒，14093520字节)*Main>；相同元素[6^60，5^50，1，5，6，6，8，9，3，4，6，6，2，4，6，1，6^60，7^70，1，1，1，3，3^30][1，2，3，4，5，6，8，9，3^30，5^50，6^60，7^70]TRUE(0.10秒，12610056字节)*Main>；相同元素[6^60，5^50，1，5，6，6，8，9，3，4，6，6，2，4，6，1，6^60，7^70，1，1，1，3，3^30][1，2，3，4，5，6，8，9，3^30，5^50，6^60，7^700]FALSE(0.12秒，17130684字节)*Main>；相同元素[6^60，5^50，1，5，6，6，8，9，3，4，6，6，2，4，6，1，6^60，7^700，1，1，1，3，3^30][1，2，3，4，5，6，8，9，3^30，5^50，6^60，7^700]True(0.12秒，17604776字节)。

人们很自然地会问是否有程序验证的应用程序。我不知道，但我和丹·吉查推测有，我们正计划调查这件事。

M.H.埃斯卡多。允许快速穷举搜索的无限集合。在LICS的2007，波兰，弗罗茨瓦夫，7月。下载配套的Haskell程序。这篇文章调查了哪种无限集允许穷举搜索。它给出了系统地从旧的构建新的可搜索集的几种算法。它还表明，对于丰富的类型集合，任何包含量词的子集也都包含搜索者。由量词构造搜索器的算法速度较慢，因此目前这一结果仅具有理论意义。但其他算法都很快。

M.H.埃斯卡多。数据类型和经典空间的综合拓扑。ENTCS，Elsevier，第87卷，第21-156页，2004年11月。我现在把这种程序类型的算法拓扑称为程序类型的算法拓扑，而不是数据类型的合成拓扑，在未来的著作中我将这样称呼它。它展示了如何将一般拓扑中的概念和定理直接映射到编程语言中(我再次使用Haskell)。但它也说明了如何将其映射回经典拓扑。穷尽可搜索集合的特征是紧致集合的计算表示。

M.H.埃斯卡多和W.K.何。顺序程序设计语言的操作域理论和拓扑结构。在第20届IEEE年度计算机科学逻辑研讨会(LICs)的论文集中，2005年6月，第427-436页。如果你想了解一些关于使用域论和拓扑学进行程序推理的知识，这是一个可能的起点。我们没有使用域理论和拓扑定义指称语义，而是直接从语言的操作语义(PCF，可以被视为Haskell的忠实子集)中提取它们，而不是旁路指称语义。定义域理论和指称语义的许多定义在这里作为定理出现。给出了Berger程序的证明，包括证明所需的一致连续模的适当概念。

达格·诺曼。用泛函计算--可计算性理论还是计算机科学？“符号逻辑公报”，12(1)：43-59,2006。这是关于高阶可计算性理论的一个很好的简史和综述(该学科是由Kleene和Kleene于20世纪50年代末创立的。

.