essay | tech | year-summary | about

返回上级菜单

关于一不小心就变成了图灵完全的...

日期：2018-02-23T00:00:00Z

最近几天没做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种证明一种语言是图灵完全语言的方法：

INPUT -> PROCESS -> OUTPUT
          ↑___|

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

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

参考资料：