图灵完备是什么意思?
你能不能给出一个简单的解释,而不是过多的理论细节?
图灵完备是什么意思?
你能不能给出一个简单的解释,而不是过多的理论细节?
当前回答
以下是最简单的解释:
图灵完备系统指的是这样一个系统,在这个系统中,可以编写程序来找到答案(尽管不保证运行时间或内存)。
所以,如果有人说“我的新东西是图灵完备的”,这意味着在原则上(尽管通常不是在实践中)它可以用来解决任何计算问题。
有时候这是个玩笑……有人用vi写了一个图灵机模拟器,所以可以说vi是世界上唯一需要的计算引擎。
其他回答
我认为“图灵完备”概念的重要性在于能够识别一台计算机(不一定是机械/电气“计算机”),它可以将其过程分解为由越来越简单的指令组成的“简单”指令,通用机可以解释并执行这些指令。
我强烈推荐《注释图灵》
@Mark,我认为你所解释的是通用图灵机和图灵完备的混合描述。
从实际意义上讲,图灵完备指的是一台机器/过程/计算,它可以被编写并表示为程序,由通用机(台式计算机)执行。虽然它不考虑时间或存储,正如其他人所提到的。
从根本上讲,图灵完备性是一个简洁的要求,即无界递归。
甚至不受记忆的限制。
我是独立思考的,但这里有一些关于这个论断的讨论。我对LSP的定义提供了更多的上下文。
这里的其他答案并没有直接定义图灵完备性的基本本质。
关系数据库能否输入地点和道路的经度和纬度,并计算它们之间的最短路径?这是一个表明SQL不是图灵完备的问题。
但是c++可以做到,并且可以解决任何问题。事实就是这样。
以下是最简单的解释:
图灵完备系统指的是这样一个系统,在这个系统中,可以编写程序来找到答案(尽管不保证运行时间或内存)。
所以,如果有人说“我的新东西是图灵完备的”,这意味着在原则上(尽管通常不是在实践中)它可以用来解决任何计算问题。
有时候这是个玩笑……有人用vi写了一个图灵机模拟器,所以可以说vi是世界上唯一需要的计算引擎。
We call a language Turing-complete if and only if (1) it is decidable by a Turing machine but (2) not by anything less capable than a Turing machine. For instance, the language of palindromes over the alphabet {a, b} is decidable by Turing machines, but also by pushdown automata; so, this language is not Turing-complete. Truly Turing-complete languages - ones that require the full computing power of Turing machines - are pretty rare. Perhaps the language of strings x.y.z where x is a number, y is a Turing-machine and z is an initial tape configuration, and y halts on z in fewer than x! steps - perhaps that qualifies (though it would need to be shown!)
A common imprecise usage confuses Turing-completeness with Turing-equivalence. Turing-equivalence refers to the property of a computational system which can simulate, and which can be simulated by, Turing machines. We might say Java is a Turing-equivalent programming language, for instance, because you can write a Turing-machine simulator in Java, and because you could define a Turing machine that simulates execution of Java programs. According to the Church-Turing thesis, Turing machines can perform any effective computation, so Turing-equivalence means a system is as capable as possible (if the Church-Turing thesis is true!)
图灵等价比真正的图灵完备性更主流;这一点以及“完全”比“等效”短的事实可能解释了为什么“图灵完全”经常被误用为图灵等效,但我离题了。