标签: turing-complete

如果一种语言具有控制结构和变量,但不支持数组,列表,内存访问和分配等,那么它是否可以完成Turing？

也许,如果没有限制,你可以创建变量的量,可以通过像创建变量模拟数组array_1,array_2...... array_6000通过他们和手动循环,并以某种方式创建复杂的数据结构和递归？

编辑:即使您不能通过名称操作访问变量(array_10+i不允许)？

我在维基百科中读到,在任意实数/有理数字段上定义的神经网络函数(以及算法模式和推测性的"transrecursive"模型)比我们今天使用的计算机具有更多的计算能力.当然这是一个俄罗斯维基百科(ru.wikipedia.org)的页面,可能没有得到适当的证明,但这不是这种谣言的唯一来源.

现在,我真正不理解的是:字符串重写机器(NN是完全字符串重写机器,就像图灵机器一样;只有编程语言不同)如何才能比普通功能的U机更强大？

是的,描述性工具确实不同,但事实是这种类的任何功能都可以(很容易或不能)变成合法的图灵机.我错了吗？我是否会错过重要的事情？

人们说这是什么原因？我知道今天已经广泛接受了不确定性的fenomenum(尽管根据我所读的内容并未得到一致证明),但我并没有真正看到NN能够解决该特定问题的可能性最小.

加载项:Not consistently proven according to what I've read- 我的意思是你可能想在90年代中期之后看看A.Zenkin的(俄罗斯数学家)论文,他有说服力地假设G. Cantor概念的错误,包括超限集,不可数集,对角化方法(图灵用于证明不可判定性的方法)和其他方法.甚至Goedel的不完备性定理也只是在21世纪才得到证实.这只是为了将Zenkin的工作插入到帖子中,因为我不知道CS社区知识的普及程度如此,如果看起来确实很愚蠢,请原谅我.

谢谢!

今天早上,我在纯HTML5 + CSS3(没有javascript)中遇到了规则110的以下实现.按顺序按Tab键和空格键以运行自动机.

http://elilies.com/rule110-full.html

我查看了源代码,但我真的无法弄清楚它是如何跟踪状态的.当按下Tab键时,我认为:焦点选择器开始播放,但我不确定按下空格时会发生什么.

我知道C++模板元编程是Turing-complete.预处理程序元编程是否同样适用？

我期待创建一个最小的,计算通用的字母数字x86操作码子集.最终我希望子集包含尽可能少的指令,如果有多个最小子集我也想知道.子集应该能够模拟可以用整套字母数字指令编写的任何程序.说明应仅涵盖与"AZ","az"和"0-9"字符对应的说明.

到目前为止,我认为一个push,pop,inc,dec,cmp,和je就足够了,但我敢肯定有一个较小的一套.我怎样才能证明我生成的集合能够使用所有字母数字指令模拟任何程序？我怎么能证明这样的一套是最小的？有谁知道这样的指令子集是否存在？

是否准确地说，在现有的图查询语言（Cypher、Datalog、Sparql 等）中，Gremlin 是唯一一种图灵完备的语言？

如果重要的话，我并不是在寻找像《万智牌》的图灵完备性证明这样的边缘情况；我的问题的目的是 Gremlin 是否是唯一适合在实践中对图执行任意计算的图查询语言。

是否可以编写一个 SELECT 语句，返回具有零行和零列的数据集？

Libra 会像以太坊一样完成图灵吗？我已经阅读了白皮书，但一直无法决定。

这是白皮书：https : //developers.libra.org/docs/assets/papers/libra-move-a-language-with-programmable-resources.pdf

今天是个好日子！

我正在尝试解决这个练习以达到学习目的。有人可以指导我解决这 3 个问题吗？

就像我尝试了第一个问题，将两个由“+”分隔的二进制数相加。我尝试通过用相应数量的 1 或零表示每个数字来进行 2 个数字加法，例如 5 = 1 1 1 1 1 或 0 0 0 0 0，然后将它们相加，结果也将采用与所表示的相同的格式，但如何添加或表示 2 个二进制文件并用 + 分隔它们，但没有得到任何线索。图灵机的头会从左边移动到+号，然后再向+号左右移动吗？但是添加将如何执行。就我所知而言，TM 不能简单地添加二进制数，我们必须制定一些逻辑来表示其二进制数，就像简单地添加 2 个数字的情况一样。比较两个二进制文件的情况是否相似？问候

Datalog不是图灵完备的。

但它的计算类是什么？

它相当于有限状态机或下推机（即上下文无关）……还是介于两者之间？