park@usceast.UUCP (Kihong Park) (01/15/90)
>In article <1990Jan12.030424.1397@world.std.com> bzs@world.std.com (Barry Shein) writes: >>The halting problem states (very roughly) "There exists at least one >>program who's halting conditions cannot be determined". >In article <1596@castle.ed.ac.uk> arshad@lfcs.ed.ac.uk (Arshad Mahmood) writes: >>No there are uncountably many of them. What does Arshad Mohmood mean there are uncountably many of them? The set of halting and non-halting turing machines forms a countably infinite set. I haven't read his posting, and hence I'm not sure if he is not referring to something else by "them".
arshad@lfcs.ed.ac.uk (Arshad Mahmood) (01/15/90)
In article <3052@usceast.UUCP> park@usceast.uucp.UUCP (Kihong Park) writes: >>In article <1990Jan12.030424.1397@world.std.com> bzs@world.std.com (Barry Shein) writes: >>>The halting problem states (very roughly) "There exists at least one >>>program who's halting conditions cannot be determined". >>In article <1596@castle.ed.ac.uk> arshad@lfcs.ed.ac.uk (Arshad Mahmood) writes: >>>No there are uncountably many of them. > >What does Arshad Mohmood mean there are uncountably many of them? The set of >halting and non-halting turing machines forms a countably infinite set. > >I haven't read his posting, and hence I'm not sure if he is not referring to >something else by "them". Perhaps I did not make it clear, what I mean is that if you write a decision procedure for checking whether a given program halts then there are uncountably many which it won't be able to decide. I am having second thoughts about this, I wish others would disregard this from my posting. The reasoning was essentailly that there is at least one which I can't decide so, I can now construct arbitrary many other programs derived from this program and I considered this set to be uncountable. This is not a theorem but I thought that it was true. If Kihong says this set is countable then I withdraw my original statement, but it still leaves a large number of examples. Sorry for cluttering comp.ai with this.