图灵完备是什么意思?
你能不能给出一个简单的解释,而不是过多的理论细节?
图灵完备是什么意思?
你能不能给出一个简单的解释,而不是过多的理论细节?
当前回答
从维基百科:
Turing completeness, named after Alan Turing, is significant in that every plausible design for a computing device so far advanced can be emulated by a universal Turing machine — an observation that has become known as the Church-Turing thesis. Thus, a machine that can act as a universal Turing machine can, in principle, perform any calculation that any other programmable computer is capable of. However, this has nothing to do with the effort required to write a program for the machine, the time it may take for the machine to perform the calculation, or any abilities the machine may possess that are unrelated to computation. While truly Turing-complete machines are very likely physically impossible, as they require unlimited storage, Turing completeness is often loosely attributed to physical machines or programming languages that would be universal if they had unlimited storage. All modern computers are Turing-complete in this sense.
我不知道你怎么能比这更非技术,除了说“图灵完备意味着‘能够在足够的时间和空间内回答可计算的问题’”。
其他回答
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!)
图灵等价比真正的图灵完备性更主流;这一点以及“完全”比“等效”短的事实可能解释了为什么“图灵完全”经常被误用为图灵等效,但我离题了。
Brasilford教授在这段视频中对所解释的内容进行了超级简短的总结。
图灵完备≅做图灵机能做的任何事情。
它具有条件分支(即。“如果声明”)。此外,暗示“go to”,因此允许循环。 它获得程序所需的任意数量的内存(例如足够长的磁带)。
从根本上讲,图灵完备性是一个简洁的要求,即无界递归。
甚至不受记忆的限制。
我是独立思考的,但这里有一些关于这个论断的讨论。我对LSP的定义提供了更多的上下文。
这里的其他答案并没有直接定义图灵完备性的基本本质。
图灵完备意味着它至少和图灵机一样强大。这意味着任何可以被图灵机计算的东西都可以被图灵完备系统计算出来。
目前还没有人发现比图灵机更强大的系统。因此,就目前而言,说一个系统是图灵完备的,就等于说这个系统与任何已知的计算系统一样强大(参见丘奇-图灵论文)。
我认为“图灵完备”概念的重要性在于能够识别一台计算机(不一定是机械/电气“计算机”),它可以将其过程分解为由越来越简单的指令组成的“简单”指令,通用机可以解释并执行这些指令。
我强烈推荐《注释图灵》
@Mark,我认为你所解释的是通用图灵机和图灵完备的混合描述。
从实际意义上讲,图灵完备指的是一台机器/过程/计算,它可以被编写并表示为程序,由通用机(台式计算机)执行。虽然它不考虑时间或存储,正如其他人所提到的。