超越图灵机

超越图灵机的条件很简单：如果一个图灵机，1，允许的状态数目是无限的，2，某些状态允许的扩展状态是无限的，3，允许的输入字符是无限的，4，允许的预先知道的内容是无限的（神谕），5，可以以无限快的速度（无限小的时间间隔）运行，6，可以接受的输入多于一个（不只在纸带上面），且多余的输入是不可由普通图灵机产生的非规则字节串，7，成为一般性的无限非确定性图灵机，8，成为概率图灵机（等价于所有的统计衍射网络），满足以上条件的任意一个或多个，都拥有了超越图灵机的能力。

因为实数可以认为是拥有无限字节的数。所以只要一个机器内部允许了实数，那么它就可以被等价为1,2,3,4,7,8中的任何一种。5这个条件需要量子力学支持。

（参考 http://arxiv.org/pdf/math.LO/0209332）

https://www.douban.com/note/94142577/