scratch写的图灵机

2018-05-28 17:54:31 浏览数 (2)

  从程序员的角度来说,大多数程序员对于scratch不感冒,因为这专门给孩子玩的。的确,积木的方式不适合专业程序员写代码,程序员也更喜欢敲键盘,但其实plc的梯形图却也算是此类(电路的原理图思维上有很大差别,属于真实电路拓扑,不能算此类)。然而别小看scratch,怎么说,它也是图灵完备的。而且,过程支持递归,虽然带不了返回值。

  虽然计算速度会很慢,但是还是可以设计出一个图灵机。

  思路其实也不是那么麻烦,scatch变量是弱类型的,支持list。虽然理论上,即便scratch没有这个list也是图灵完备的,但毕竟要麻烦好多。

  我们制作图灵机,则利用list来放图灵机的纸带。图灵机的各种规则当然也要放list上,规则是{x||x为状态}、{x|x为纸带值}、{x||x为状态}、{x|x为纸带值}、{左,右}上的一个五元关系,代表着当前状态、当前纸带值、将来状态、将来纸带值、磁头方向。为了方便,分5个list来装。当然,状态、纸带值都用0开始的整数来表示就已经可以,左右用01表示。另外,初始状态为1,接受状态为1,拒绝状态为2。

  图灵机的运行并不复杂,这里不赘述,忘记怎么运行的请参考https://en.wikipedia.org/wiki/Turing_machine

  以下是图灵机:

输入图灵机的参数

设置纸带的初始值

图灵机的运行过程

显示运行结果

点小旗触发全套动作

  哈哈,麻雀虽小,五脏俱全。虽然scratch只是孩子玩的东西,它理论上却可以实现所有的可运算,很神奇不是吗?

0 人点赞