Wednesday, June 16, 2010

Cantor's Diagonalization Argument, Halting Problem (cont..)

This is another thing that has been the cause of some worry for me in the past (see this) This topic was brought up again when i came across this link. Following are my thoughts about this :

(1) todo: draw picture of set with inf. elements & argue why its countably infinite.
(2) todo: how sorting affects ordinality & but leaves cardinality unchanged
(3) todo: what "diagonalize" means:
(4) todo: Why diagonalization leads to a set with cardinality larger then what we started off with.
Now, onto another topic that has been of interest to me:
How the Halting Problem is related to the Russel's paradox. As i see it today, it is related only in the sense that questions asked (for problems being solved) in both of these lead to absurd conclusions (against the rules of logic), and thus, there must be something innately wrong somewhere. With Russel's Paradox, what is wrong is the definition of a 'set', and with the Halting problem, what is wrong is the expectation that we can write a program that will tell us whether a program will halt given a certain input.

Also, here is a wonderful link to set-theory questions. (in fact this site has answers to tonnes questions & will follow up more about that soon)

No comments: