首页
学习
活动
专区
圈层
工具
发布
社区首页 >问答首页 >在给定语言中证明函数的不可表达性

问在给定语言中证明函数的不可表达性
EN

Stack Overflow用户
提问于 2020-12-13 21:16:07
回答 2查看 68关注 0票数 1

我目前正在阅读JohnC.Mitchell的编程语言基础。实际上,练习2.2.3要求读者展示(自然数)指数函数不能通过一种小型语言的表达式隐式定义。该语言由自然数和对所述数字的加法(以及布尔值、自然数相等谓词&三元条件)组成。这里没有循环、递归结构或定点组合器.以下是精确的语法:

代码语言:javascript
复制
<bool_exp> ::= <bool_var> | true | false | Eq? <nat_exp> <nat_exp> |
               if <bool_exp> then <bool_exp> else <bool_exp>
<nat_exp>  ::= <nat_var> | 0 | 1 | 2 | … | <nat_exp> + <nat_exp> |
               if <bool_exp> then <nat_exp> else <nat_exp>

同样,该对象是为了表明,不能通过这种语言中的表达式隐式定义指数函数n^m。

直觉上,我愿意接受这一点。如果我们认为指数是重复的乘法,我们似乎不能用这种语言来表达这一点。但如何才能正式证明这一点呢?更广泛地说,如何证明一种语言的表达式不能用另一种语言表达?

EN

回答 2

Stack Overflow用户

回答已采纳

发布于 2020-12-14 11:43:18

没有解决办法,只是暗示:

首先,让我指出,如果语言中有有限多个数字,那么指数可以定义为一个表达式。(当真正的结果无法表示时,你必须定义它应该产生什么结果(如概括)。想想为什么。

提示:假设只有两个数字,0和1。您能写出一个包含m和n的表达式,其结果是n^m吗?如果有三个数字: 0,1和2呢?如果有四个呢?等等..。

为什么这些解决方案都不起作用?让我们对它们进行索引,并调用{0,1} partial_solution_1的解决方案,调用{0,1,2} partial_solution_2的解决方案,等等。为什么partial_solution_n不是所有自然数集合的解决方案?

也许你可以用某种度量的f : Expression -> Nat来概括这一点,这样每个带有f(expr) < n的表达式expr都是错误的。

你可能会从欧几里得的策略中得到一些启示,证明有无限多的素数。

票数 1
EN

Stack Overflow用户

发布于 2020-12-14 12:56:18

这里有一个简单的思考方法:表达式有一个固定的、有限的大小,它可以做的唯一算术操作是生成不是以文字形式写的数字,也不是作为变量值提供的数字。因此,它可能产生的最大数被加法加1的数目所限制,乘以表达式中涉及的最大数。

因此,给定一个提议的表达式,k是其中的加法数,c是最大的文字(如果没有,则为1)并选择m和n,使n^m > (k+1)*max(m,n,c)。则该输入的表达式的结果不能是正确的结果。

请注意,这个证明依赖于允许任意大的数字的语言,正如在另一个答案中所指出的。

票数 2
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/65280759

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档