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