从程序员的角度来说, 大多数程序员对于 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 只是孩子玩的东西, 它理论上却可以实现所有的可运算, 很神奇不是吗?
来源: https://www.cnblogs.com/Colin-Cai/p/8972752.html