返回列表

最小图灵完备语言

默认分类 2014/07/30 07:06

原文地址: http://www.cnblogs.com/DSharp/archive/2013/05/22/3093750.html

Brainfuck是一种极小化的计算机语言,它是由Urban Müller在1993年创建的.

Müller的目标是建立一种简单的、可以用最小的编译器来实现的、符合图灵完全思想的编程语言。这种语言由八种状态构成,为Amiga机器编写的编译器(第二版)只有240个字节大小! 就象它的名字所暗示的,brainfuck程序很难读懂。尽管如此,brainfuck图灵机一样可以完成任何计算任务。虽然brainfuck的计算方式如此与众不同,但它确实能够正确运行。 这种语言基于一个简单的机器模型,除了指令,这个机器还包括:一个以字节为单位、被初始化为零的数组、一个指向该数组的指针(初始时指向数组的第一个字节)、以及用于输入输出的两个字节流。 这种 语言,是一种按照“Turing complete(完整图灵机)”思想设计的语言,它的主要设计思路是:用最小的概念实现一种“简单”的语言,BrainF**k 语言只有八种符号,所有的操作都由这八种符号的组合来完成。

由此可见,设计一门语言,只要达到图灵完备即可,而达到它的最小集是如此之小,相信3分钟就能看完,而一个完整的编译器,仅仅只有240字节,也就是不到一条微博的数据量(一汉字相当于2字节,新浪微博一条是140字)

这个事实告诉我们,其实很多理论,其实都是很简单的.能和不能之间,就是隔着一张纸,很多时候我们就是怕伤了手指头把自已给困住了.

而能用到功能强大,还有很长的路要走,至少有工作量这个严重问题.不过好在,中国有世界上最多的人口.