24小时热门版块排行榜

新虫 (初入文坛)

[求助] 图灵机全体是可数的吗

所以图灵机应该可以组成一个集合吗？（或者说一台通用图灵机的程序全体可以组成一个集合吗？）
如果可以，那这个集合是可数的吗？
如果不可以，谁知道这样定义集合哪里有问题，是出现了自指代问题吗？
图灵机的定义图灵机-维基百科有兴趣的去看看，一起来讨论。

1楼 2014-09-26 19:27:55

已阅回复此楼关注TA 给TA发消息送TA红花 TA的回帖

荣誉版主 (文坛精英)

2楼2014-09-26 20:08:10

已阅回复此楼关注TA 给TA发消息送TA红花 TA的回帖

新虫 (初入文坛)

引用回帖:

2楼: Originally posted by feixiaolin at 2014-09-26 20:08:10
http://blog.sina.com.cn/s/blog_4dff87120100ylfv.html

图灵机集合是可数的,那么难道某些实数不能用图灵机生成？比如 $\pi\$ ，应该可以设计一个图灵机不断的在纸袋上输出 $\pi\$ 的各个位数（当然是二进制的，另外纸袋上可以每隔一位取一位作为输出为，另外的一位作为计算的缓存）。可是实数是不可数的啊。（所以实数比所以程序多）

3楼2014-09-28 09:37:05

已阅回复此楼关注TA 给TA发消息送TA红花 TA的回帖

相关版块跳转我要订阅楼主 houyunju1 的主题更新