相关疑难解决方法(0)

什么是图灵完成?

"图灵完成"的含义是什么意思?

你可以给出一个简单的解释,而不会涉及太多的理论细节吗?

theory turing-machines turing-complete

461
推荐指数
8
解决办法
15万
查看次数

确定它是否是编程语言的标准

告诉XY (或不是)编程语言所需的标准或基本功能什么?

我已经做了一些阅读(是HTML视为一种编程语言?,图灵完备,和其他人),来到一个语言或语法必须结束图灵完整被视为一种编程语言.它是否正确?够了吗?

我如何确定图灵是否完整?有没有具体的标准?

是否具有控制流结构(条件语句和循环)足以被视为图灵完成

programming-languages turing-complete

9
推荐指数
2
解决办法
5622
查看次数

基于堆栈的语言的图灵完备性证明

我正在编写一种基于堆栈操作的笑话语言。我试图找到使其图灵完备所需的最少指令量,但不知道基于一个堆栈的语言是否可以图灵完备。这些说明足够吗?

IF (top of stack is non-zero)
WHILE (top of stack is non-zero)
PUSH [n-bit integer (where n is a natural number)]
POP
SWAP (top two values)
DUPLICATE (top value)
PLUS (adds top two values, pops them, and pushes result)
Run Code Online (Sandbox Code Playgroud)

我已经查看了几个问题和答案(例如这个这个),并相信上述说明已经足够了。我对么?或者我是否需要其他东西,例如函数调用、变量或另一个堆栈?

如果这些说明足够了,其中有哪些是多余的吗?


编辑:通过添加ROTATE命令(将堆栈的前三个值从 更改A B CB C A)并消除DUPLICATEPLUSSWAP命令,可以实现规则 110 元胞自动机的 3 个字符版本。这足以证明图灵完整性吗?

如果有一个没有变量或函数的图灵完整单栈语言的例子那就太好了。

stack programming-languages turing-complete

4
推荐指数
1
解决办法
1720
查看次数