图灵完备是什么意思?
你能不能给出一个简单的解释,而不是过多的理论细节?
图灵完备是什么意思?
你能不能给出一个简单的解释,而不是过多的理论细节?
当前回答
用最简单的术语来说,图灵完备系统可以解决任何可能的计算问题。
关键要求之一是便签大小不受限制,并且可以倒带访问之前对便签的写操作。
因此在实践中没有一个系统是图灵完备的。
相反,有些系统通过对无界内存建模并执行任何可能的计算来接近图灵完备性。
其他回答
正如韦伦·弗林所说:
图灵完备意味着它至少和图灵机一样强大。
我认为这是不正确的,如果一个系统和图灵机一样强大,那么它就是图灵完备的,即机器所做的每一个计算都可以由系统完成,而且系统所做的每一个计算都可以由图灵机完成。
我认为“图灵完备”概念的重要性在于能够识别一台计算机(不一定是机械/电气“计算机”),它可以将其过程分解为由越来越简单的指令组成的“简单”指令,通用机可以解释并执行这些指令。
我强烈推荐《注释图灵》
@Mark,我认为你所解释的是通用图灵机和图灵完备的混合描述。
从实际意义上讲,图灵完备指的是一台机器/过程/计算,它可以被编写并表示为程序,由通用机(台式计算机)执行。虽然它不考虑时间或存储,正如其他人所提到的。
从维基百科:
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.
我不知道你怎么能比这更非技术,除了说“图灵完备意味着‘能够在足够的时间和空间内回答可计算的问题’”。
以下是最简单的解释:
图灵完备系统指的是这样一个系统,在这个系统中,可以编写程序来找到答案(尽管不保证运行时间或内存)。
所以,如果有人说“我的新东西是图灵完备的”,这意味着在原则上(尽管通常不是在实践中)它可以用来解决任何计算问题。
有时候这是个玩笑……有人用vi写了一个图灵机模拟器,所以可以说vi是世界上唯一需要的计算引擎。
用最简单的术语来说,图灵完备系统可以解决任何可能的计算问题。
关键要求之一是便签大小不受限制,并且可以倒带访问之前对便签的写操作。
因此在实践中没有一个系统是图灵完备的。
相反,有些系统通过对无界内存建模并执行任何可能的计算来接近图灵完备性。