[计算理论] 图灵机和简单语言

soloforce

前些天偶然看到的关于图灵机和“简单语言”的介绍，挺有趣的。
图灵机听说的比较多；“简单语言”则是第一次接触到，先说说它吧。当然，凡是接触过计算理论的朋友对什么图灵机、歌德尔数、停机问题等等都有了解，而我只是一个外行新手。

[color="Blue"]简单语言：只有“自加”、“自减”、“循环” 这三种语句的语言（真是够简单的:yun:）
[color="Blue"]其他假定：只有整数运算（浮点数可以通过整数模拟）；另外还有存储器支持（内存或外存），就是说无论是变量还是常数，都分配有一个存储器地址（且假定存储器无限大）。

数学家们目前认为图灵机和简单语言是等价的。自加、自减、循环语句，貌似无法完成高级语言中各种复杂的语义动作，其实不然，简单语言的能力和C、C++、Java、Pascal之类的高级语言是等价的，也就是说，目前流行的高级语言的功能都可以用简单语言来实现！下面举一些例子说明简单语言是如何实现赋值、相加、相减、条件判断等高级语言中的语句的：

我用C语言来模拟简单语言的基本语句（当然，只能用C语言中的"++,--,while"三种语句，还有是变量定义语句（相当于分配存储器））。

0、基本类型

2. typedef short TYPE;
4. /*******************************
5. Basic operation definitions.
6. ALL the operands (i.e. x,y,z,tmp etc.)
7. should be TYPE variables
8. *******************************/

复制代码

1、先看看如何把一个变量x置为0

2. /* reset x to 0.
3. when x is large, it sucks :-< */
4. #define _SLOW_RESET(x) while(x){ --x; }
6. /* fast reset x to 0.
7. this version BREAKS the SIMPLE LANGUAGE RULES,
8. however it's fast, you know why :-) */
9. #define _FAST_RESET(x) x&=0
11. /* The default RESET edition is the slow one, to obey the rules.
12. You can set it to the fast one by defining compiling parameters, like
13. "-DFAST_RESET" for gcc compiler. */
14. #ifdef FAST_RESET
15.     #define RESET(x) _FAST_RESET(x)
16. #else
17.     #define RESET(x) _SLOW_RESET(x)
18. #endif

复制代码

2、赋值语句

2. /* x:=y; value of y won't be altered */
3. #define ASSIGN(x,y) do{\
4.         RESET(x); \
5.         TYPE tmp1;\
6.         RESET(tmp1);\
7.         while(y){\
8.             ++x;\
9.             ++tmp1;\
10.             --y;\
11.         }\
12.         while(tmp1){\
13.             ++y;\
14.             --tmp1;\
15.         }\
16.     }while(0)

复制代码

3、加法语句

2. /* x:=y+z; values of y,z won't be altered */
3. #define ADD(x,y,z) do{\
4.         ASSIGN(x,y);\
5.         TYPE tmp2;\
6.         ASSIGN(tmp2,z);\
7.         while(tmp2){\
8.             ++x;\
9.             --tmp2;\
10.         }\
11.     }while(0)

复制代码

4、减法语句

2. /* x:=y-z; values of y,z won't be altered */
3. #define SUB(x,y,z) do{\
4.         ASSIGN(x,y);\
5.         TYPE tmp3;\
6.         ASSIGN(tmp3,z);\
7.         while(tmp3){\
8.             --x;\
9.             --tmp3;\
10.         }\
11.     }while(0)

复制代码

xiaorui

简单 ＋ 简单 ＝复杂 。
其实多了就是 复杂

老头也疯狂

呵呵2楼说的对多了就复杂了

zxd123314

那么说如何实现if语句？？

木人

内存地址， 地址一个编号。所有信息都是整数。
if的条件可以用简单语句判断， 貌似简单语句可以完成所有吧。