水木清华校友基金袁晔:图灵完备需要自动机的知识

时间 : 18-11-01 栏目 : ag电子捕鱼 作者 : admin 评论 : 0 点击 : 124 次

  图灵完备需要自动机的知识。人们很好奇需要什么样的机器才能表达出某种语言。

  大致可以分为有限状态自动机,下推自动机和图灵机那么几档。前者所能表达的语言是后者的真子集。

  有限状态自动机只能表达正则语言。下退自动机能够表达上下文无关语言。而图灵机的语言是递归可枚举语言。不过也有语言不是图灵机表达得了的,比如对角语言。

  图灵机可以对应到一个字符串,并被别的图灵机模拟。能够模拟图灵机,则称之为图灵完备,当然,图灵机可以模拟有限状态自动机和下推自动机。

  P和NP分别是确定型图灵机和非确定型图灵机在多项式的推演步骤下,所能表达的语言集合。

  这两类图灵机所能表达的语言集合是一样的。就是多项式推演步骤这个条件一加,就未解之谜了。

  可判定性问题,许多问题还真不是图灵机能解决的,比如:图灵机不能表达的语言。著名的问题有图灵机停机问题。

  P与NP其实都是可判定问题,他们其实都是指多项式时间内可判定,只是需要动用非确定型图灵机。

  图灵不完备的语言常见原因有循环或递归受限,比如:无法写不终止的程序,无法实现类似数组或列表这样的数据结构,使能写的程序有限。

  图灵完备可能带来坏处, 如C++模板语言是在类型检查时执行,如果编译器不检查,我们完全可以写出使得C++编译器陷入死循环的程序。

  图灵不完备也不是没有意义,有些场景我们需要限制语言本身,比如:限制循环和递归,可以保证该编程语言能写的程序一定是终止的。

本文标签

除非注明,文章均为( admin )原创,转载请保留链接: http://www.treslola.com/?p=276

水木清华校友基金袁晔:图灵完备需要自动机的知识:等您坐沙发呢!

发表评论


-----===== 博主信息 =====-----

为您推荐

0