程序人生

图灵完备的理解

Reference

https://www.zhihu.com/question/20115374

Overview

图灵完备是相对于一套操作来说的,是可以实现图灵机中所有功能的。

这套操作可以是

  • 一种指令集
  • 一种编程语言

那么什么是图灵机?

谁是图灵呢?

  • 关于图灵 推荐一下 《The Imitation Game》,传记类电影可以稍作了解。
  • 计算机届有个 叫做 图灵奖 的 可以类比 诺贝尔奖
  • 来纪念 图灵 提出的 计算机的数学模型,我们称之为 图灵机。
    • 一条无限长的纸带 (可以理解为现在的内存系统)
    • 一张字符表 (类似ASIIC)
    • 一个读写头 (相当于一个 指针,或者理解为pc)
    • 一个状态寄存器 (可以理解为 保存 当前上下文的寄存器)
    • 一个有限指令集 (ISA : load、store、jump、+-、shift)

一个类似图灵机的有趣的语言 Brainfuck

Quick Reference

>increment the data pointer (to point to the next cell to the right).
<decrement the data pointer (to point to the next cell to the left).
+increment (increase by one) the byte at the data pointer.
-decrement (decrease by one) the byte at the data pointer.
.output the byte at the data pointer.
,accept one byte of input, storing its value in the byte at the data pointer.
[if the byte at the data pointer is zero, then instead of moving the instruction pointer forward to the next command, jump it forward to the command after the matching ] command.
]if the byte at the data pointer is nonzero, then instead of moving the instruction pointer forward to the next command, jump it back to the command after the matching [ command.
!if the exclaim box is checked, allows the interpreter to use all characters to the right of the ! as program input.

可视化的模拟器,动图非常有意思

http://fatiherikli.github.io/brainfuck-visualizer/

wiki

http://en.wikipedia.org/wiki/Brainfuck