来讨论讨论逻辑和可计算性

sfatsdu · 发表于 2005-7-23 12:57:56

i是自然数
如果odd,就变成3i+1
如果even,就变成i/2
请问最终总能够变成1么?

lollipop · 发表于 2005-7-25 09:44:51

MS可以，可是偶不是数学大师，证明不出来，呵呵
很久以前用BASIC写了个程序，可惜机器太烂，算了几十分钟才验证到300，000

conwood · 发表于 2005-8-1 00:05:47

停机问题的列子，假设存在函数 a()
接受的参数是另一个函数b，a 的职责是判断 b 是否会在有限时间内终止

那么考虑这个函数

c()
{
if(a(c)==true)
while(true);
else
exit;
}

复制代码

gaowenmei · 发表于 2007-8-25 19:59:24

停机问题还是第一次听说，汗！~

zhenghj1024 · 发表于 2007-8-25 22:09:47

简单来说: 可计算性就是研究问题能不能算出来，计算复杂性就是研究问题有多难算。

colinzhengj · 发表于 2007-10-5 09:54:46

楼主怎么什么也没讨论？
计算理论这方面，recursive sets/RE sets只是一个开头。recursion theory 的内容很多，技巧也很多。推荐一份notes: http://www.comp.nus.edu.sg/~fstephan/recursiontheory.pdf
能真正理解前一半内容的证明，就应该算入门了
cs的角度的可计算性，简单一些，前3章就包括了主要内容。cs的可计算性还包括各种 automata 和recursive sets的一些子集：context free language, regular expression 等。这些相对简单一些

minus273 · 发表于 2007-10-30 05:04:39

现在又在整天被可计算性和逻辑折磨了
来看看老帖子恩
其实这些东西一直就没怎么好好学过
哎

minus273 · 发表于 2007-10-30 05:06:22

Post by sfatsdu
i是自然数
如果odd,就变成3i+1
如果even,就变成i/2
请问最终总能够变成1么?

想到Goodstein序列问题
在Peano公理系统里面可以表述，而且在标准的整数模型里面是真的
但是用Peano公理系统不能证明
听起来挺好玩儿的

LovePoPo · 发表于 2007-11-14 08:41:43

这个主题很难了

呵呵,我们学校的杀手课程

这个课程是我们计算机院很资深教授开的,可是每次只有不到10个人去选,上的人更少,lol

zhangwei_7417 · 发表于 2007-12-3 18:44:21

我也是第一次听说这些得哦,汗颜.

		自动登录	找回密码
密码			注册