|
前些天偶然看到的关于图灵机和“简单语言”的介绍,挺有趣的。
图灵机听说的比较多;“简单语言”则是第一次接触到,先说说它吧。当然,凡是接触过计算理论的朋友对什么图灵机、歌德尔数、停机问题等等都有了解,而我只是一个外行新手。
[color="Blue"]简单语言:只有“自加”、“自减”、“循环” 这三种语句的语言(真是够简单的:yun:)
[color="Blue"]其他假定:只有整数运算(浮点数可以通过整数模拟);另外还有存储器支持(内存或外存),就是说无论是变量还是常数,都分配有一个存储器地址(且假定存储器无限大)。
数学家们目前认为图灵机和简单语言是等价的。自加、自减、循环语句,貌似无法完成高级语言中各种复杂的语义动作,其实不然,简单语言的能力和C、C++、Java、Pascal之类的高级语言是等价的,也就是说,目前流行的高级语言的功能都可以用简单语言来实现!下面举一些例子说明简单语言是如何实现赋值、相加、相减、条件判断等高级语言中的语句的:
我用C语言来模拟简单语言的基本语句(当然,只能用C语言中的"++,--,while"三种语句,还有是变量定义语句(相当于分配存储器))。
0、基本类型- typedef short TYPE;
- /*******************************
- Basic operation definitions.
- ALL the operands (i.e. x,y,z,tmp etc.)
- should be TYPE variables
- *******************************/
复制代码
1、先看看如何把一个变量x置为0- /* reset x to 0.
- when x is large, it sucks :-< */
- #define _SLOW_RESET(x) while(x){ --x; }
- /* fast reset x to 0.
- this version BREAKS the SIMPLE LANGUAGE RULES,
- however it's fast, you know why :-) */
- #define _FAST_RESET(x) x&=0
- /* The default RESET edition is the slow one, to obey the rules.
- You can set it to the fast one by defining compiling parameters, like
- "-DFAST_RESET" for gcc compiler. */
- #ifdef FAST_RESET
- #define RESET(x) _FAST_RESET(x)
- #else
- #define RESET(x) _SLOW_RESET(x)
- #endif
复制代码
2、赋值语句- /* x:=y; value of y won't be altered */
- #define ASSIGN(x,y) do{\
- RESET(x); \
- TYPE tmp1;\
- RESET(tmp1);\
- while(y){\
- ++x;\
- ++tmp1;\
- --y;\
- }\
- while(tmp1){\
- ++y;\
- --tmp1;\
- }\
- }while(0)
复制代码
3、加法语句- /* x:=y+z; values of y,z won't be altered */
- #define ADD(x,y,z) do{\
- ASSIGN(x,y);\
- TYPE tmp2;\
- ASSIGN(tmp2,z);\
- while(tmp2){\
- ++x;\
- --tmp2;\
- }\
- }while(0)
复制代码
4、减法语句- /* x:=y-z; values of y,z won't be altered */
- #define SUB(x,y,z) do{\
- ASSIGN(x,y);\
- TYPE tmp3;\
- ASSIGN(tmp3,z);\
- while(tmp3){\
- --x;\
- --tmp3;\
- }\
- }while(0)
复制代码 |
|