最近几天没做leetcode的题,工作太忙了。明明就要离职了55555…. 就顺便偷个懒,写点好玩的东西。主要内容和灵感来自这篇文章(https://cpplover.blogspot.jp/2013/10/blog-post_20.html)

1.什么是图灵完全

首先我们要明确一个概念。什么算是图灵完全。 简单来说,就是跟万能图灵机具有同等计算能力的计算模型,就可以称之为图灵完全。 图灵机可以看作是当代计算机的简化模型。基本上图灵机就是抽象化的基本计算机模型。

一般而言,大多数当代的编程语言都是图灵完全的语言。 跟NP的概念很类似,同样具有图灵机概念的话,理论上互相做的事情都可以相互转换。 也就是说,c++能做的到的大多数事情,js同样也可以做到。

再譬如令人惊讶的brainfuck这门语言,也同样是图灵完全语言。那么理论上,可以用c来bind brainfuck, brain来bind c就算了….c写的东西可以转换成brainfuck,brainfuck写的东西也可以转换成c。

我目前知道的4种证明一种语言是图灵完全语言的方法:

  • 1.用这种语言实现重复处理。(也就是可以实现finite automaton)
  • 2.用这种语言实现rule 110
  • 3.用这种语言实现life
  • 4.用某种语言制作可以另一种已经被证明是图灵完全的语言的complier来证明,这个语言是图灵完全。(这个可以说是不用证明)
1
2
INPUT -> PROCESS -> OUTPUT
          ↑___|

2.不小心就变成图灵完全的…

写完之后才发现其实要看的东西还蛮多的,很多基础概念要么就是忘记了,要么就是原本就搞得不太清楚….

参考资料:


creativ common license