版权申明：本文为博主窗户(Colin Cai)原创，欢迎转帖。如要转贴，必须注明原文网址

　　http://www.cnblogs.com/Colin-Cai/p/8972752.html 

　　作者：窗户

　　QQ：6679072

　　E-mail：6679072@qq.com

　　从程序员的角度来说，大多数程序员对于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只是孩子玩的东西，它理论上却可以实现所有的可运算，很神奇不是吗？

　　程序文件下载:

 

版权声明：本文为Colin-Cai原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://www.cnblogs.com/Colin-Cai/p/8972752.html