图灵完备的理解

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

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