图灵完备是什么意思?
你能不能给出一个简单的解释,而不是过多的理论细节?
图灵完备是什么意思?
你能不能给出一个简单的解释,而不是过多的理论细节?
当前回答
这是最简单的解释
艾伦·图灵创造了一台机器,它可以接收程序,运行程序,并显示结果。但是他必须为不同的程序创造不同的机器。所以他发明了“通用图灵机”,可以接收并运行任何程序。
编程语言类似于这些机器(尽管是虚拟的)。他们获取程序并运行它们。现在,一种编程语言被称为“图灵完备”,如果它可以运行图灵机在足够的时间和内存下可以运行的任何程序(无论哪种语言)。
例如:假设有一个程序需要10个数字并将它们相加。图灵机可以很容易地运行这个程序。但是现在想象一下,由于某种原因,您的编程语言不能执行相同的加法。这将使它成为“图灵不完整”(可以这么说)。另一方面,如果它能运行通用图灵机能运行的任何程序,那么它就是图灵完备的。
大多数现代编程语言(如Java、JavaScript、Perl等)都是图灵完备语言,因为它们都实现了运行程序所需的所有功能,如加法、乘法、if-else条件、返回语句、存储/检索/擦除数据的方法等等。
更新:你可以在我的博客文章中了解更多:“JavaScript是图灵完备的”-已解释
其他回答
用最简单的术语来说,图灵完备系统可以解决任何可能的计算问题。
关键要求之一是便签大小不受限制,并且可以倒带访问之前对便签的写操作。
因此在实践中没有一个系统是图灵完备的。
相反,有些系统通过对无界内存建模并执行任何可能的计算来接近图灵完备性。
这是最简单的解释
艾伦·图灵创造了一台机器,它可以接收程序,运行程序,并显示结果。但是他必须为不同的程序创造不同的机器。所以他发明了“通用图灵机”,可以接收并运行任何程序。
编程语言类似于这些机器(尽管是虚拟的)。他们获取程序并运行它们。现在,一种编程语言被称为“图灵完备”,如果它可以运行图灵机在足够的时间和内存下可以运行的任何程序(无论哪种语言)。
例如:假设有一个程序需要10个数字并将它们相加。图灵机可以很容易地运行这个程序。但是现在想象一下,由于某种原因,您的编程语言不能执行相同的加法。这将使它成为“图灵不完整”(可以这么说)。另一方面,如果它能运行通用图灵机能运行的任何程序,那么它就是图灵完备的。
大多数现代编程语言(如Java、JavaScript、Perl等)都是图灵完备语言,因为它们都实现了运行程序所需的所有功能,如加法、乘法、if-else条件、返回语句、存储/检索/擦除数据的方法等等。
更新:你可以在我的博客文章中了解更多:“JavaScript是图灵完备的”-已解释
图灵完备意味着它至少和图灵机一样强大。这意味着任何可以被图灵机计算的东西都可以被图灵完备系统计算出来。
目前还没有人发现比图灵机更强大的系统。因此,就目前而言,说一个系统是图灵完备的,就等于说这个系统与任何已知的计算系统一样强大(参见丘奇-图灵论文)。
我认为“图灵完备”概念的重要性在于能够识别一台计算机(不一定是机械/电气“计算机”),它可以将其过程分解为由越来越简单的指令组成的“简单”指令,通用机可以解释并执行这些指令。
我强烈推荐《注释图灵》
@Mark,我认为你所解释的是通用图灵机和图灵完备的混合描述。
从实际意义上讲,图灵完备指的是一台机器/过程/计算,它可以被编写并表示为程序,由通用机(台式计算机)执行。虽然它不考虑时间或存储,正如其他人所提到的。
Brasilford教授在这段视频中对所解释的内容进行了超级简短的总结。
图灵完备≅做图灵机能做的任何事情。
它具有条件分支(即。“如果声明”)。此外,暗示“go to”,因此允许循环。 它获得程序所需的任意数量的内存(例如足够长的磁带)。