为什么几种简单的语句就可以写出所有的程序

[fihopzz]

一直我都没想明白这是为什么？
1 简单语句
2 if或者其它条件语句
3 for或者其它循环语句
4 break，continue语句
这四种基本语句就可以组合成所有的程序。这个命题是真的吗？如果答案肯定的，有什么证明吗？我想是否应该涉及的逻辑学中的知识。

[Changsheng Jiang]

你只需要说明这几个语句可以模仿图林机

Yours Sincerely,
Changsheng Jiang

2009/1/1 fihopzz <xia...@gmail.com>

[Zoom.Quiet]

2009/1/1 fihopzz <xia...@gmail.com>:

这和逻辑学关系不大吧，是数学哪，，，

--
http://zoomquiet.org
'''过程改进乃是催生可促生靠谱的人的组织!'''
PE keeps evolving organizations which promoting people be good!

[McCAT]

这个Dijkstra好像有相关证明的

2009/1/1 fihopzz <xia...@gmail.com>:

[est]

所谓的图灵完整？呵呵。

2009/1/1 fihopzz <xia...@gmail.com>

[果]

只要 + - , . < > [ ] 八个符号就够了呢 ( BF 语言 )
参考:
http://en.wikipedia.org/wiki/Brainfuck
http://en.wikipedia.org/wiki/Computable_function
http://en.wikipedia.org/wiki/Turing_complete

[Mingli Yuan]

理论上的结论请参考：
http://en.wikipedia.org/wiki/Structured_program_theorem

实践中的讨论参考：
http://en.wikipedia.org/wiki/Structured_programming
http://en.wikipedia.org/wiki/Goto

程序设计语言中好老的公案了。

2009/1/1 果 <iamy...@gmail.com>

[kuku]

这个贴太水了吧。

[jrckkyy]

哥德尔完备性

[Li Xunhao]

赞！说得真好！

我们平常用的C，C++，JAVA语句由sequence, selection和iteration三种结构组成，
他们可以构成Chomsky 2型语言（上下文无关语言），
而2型语言又是0型语言的一个子集（递归可枚举语言），
而0型语言可以完整表示所有确定性图灵机可计算语句，
而图灵机又是建立在Kurt Godel的证明上的。

2009/1/2 jrckkyy <jrc...@gmail.com>:
> 哥德尔完备性

--

Xunhao Li
Department of Computing Science
University of Alberta
Edmonton, Alberta, Canada

[legendsland]

嘿嘿，还有一个让你更想不明白的问题：

1 简单语句
2 if或者其它条件语句
3 for或者其它循环语句
4 break，continue语句

这四种基本语句就可以组合成所有有用或者可以卖到钱的程序吗？

2009/1/1 fihopzz <xia...@gmail.com>

[Jawley]

为什么不说0和1两个数字就可以组合成所有的程序呢？我认为这一命题意义不大。呵呵

2009/1/1 fihopzz <xia...@gmail.com>

[@@]

我也刚想这么说:P

发现已经有人写了。。

2009/1/3 Jawley <jaw...@gmail.com>

[Mingli Yuan]

fihopzz 兄的这个命题是有意义的，建议多去修一些计算理论方面的课程，或者去读一些相关的资料。
真的想作语言方面的研究和实践，这些知识是少不了的。

"0和1两个数字就可以组合成所有的程序"，这个仅仅是编码，而非计算。计算在编码之后，往往涉及变换和组合。

2009/1/3 @@ <ask...@gmail.com>

[chao lu]

有道理

2009/1/3 Mingli Yuan <mingl...@gmail.com>

--
Terry Lu
Department of Service Science and Engineering
Peking University
M.P: 0086-134-886-90089
Email: luc...@pku.edu.cn
MSN Messenger: luch...@126.com

[free.wang]

顺序  递归或者循环 跳转。
这3个可以完成计算机可计算问题的所有计算。

2009/1/3 chao lu <luch...@gmail.com>

--
真正的杰出，不是妙用规则的错层，而是极致的偏执于信念.
The Crankiness of  Belief achieves Greate , not the Trick of Regulation.

[MIK]

所有的程序,这个说法太不严谨了.程序是指定计算机运行的指令的集合.
我猜想楼主想说的是可计算的问题.

[重张]

对的。

2009/1/5 MIK <china...@gmail.com>

[learn]

小时候感觉就电阻和三级管就能构造出发声电路，那才叫奇妙呢

2009/1/5 重张 <xia...@gmail.com>

[lvhuiwei at gmail.com]

Xunhao 你好，

我查了一下wikipedia，能找到Gödel's completeness theorem，图灵机的论文我也看了，但是不知道图灵机为什么建立
在Kurt Godel的证明上。请教一下。

--
Huiwei Lv
http://sites.google.com/site/lvhuiwei/

On Jan 3, 1:53 am, "Li Xunhao" <dante.hay...@gmail.com> wrote:
> 赞！说得真好！
>
> 我们平常用的C，C++，JAVA语句由sequence, selection和iteration三种结构组成，
> 他们可以构成Chomsky 2型语言（上下文无关语言），
> 而2型语言又是0型语言的一个子集（递归可枚举语言），
> 而0型语言可以完整表示所有确定性图灵机可计算语句，
> 而图灵机又是建立在Kurt Godel的证明上的。
>

> 2009/1/2 jrckkyy <jrck...@gmail.com>:

[Li Xunhao]

你好啊，我的想法是这样的，不知道对不对，请指教：

首先Kurt Godel给出了形式数学推导可以被编码的解，然后图灵据此在图灵机上编码。
图灵的编码是用一阶逻辑推导，而一阶逻辑推导的正确性由Godel's completeness保证。

2009/2/12 lvhuiwei at gmail.com <lvhu...@gmail.com>:

--

Sent from: Edmonton Ab Canada.

[pongba]

去翻翻 wikipedia ，从 turing complete 开始翻。
或者找本计算理论的入门基础教程看前几章。

2009/1/1 fihopzz <xia...@gmail.com>

--
刘未鹏(pongba)
Blog | Mind Hacks
http://mindhacks.cn
TopLanguage
http://groups.google.com/group/pongba