[comp.ai] reasons why you don't proof your programs are correct

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.