Noldorin

London, United Kingdom

noldorin.com

Age: 25

entrepreneur; graduate in mathematics / theoretical computer science / theoretical physics; polymath-in-training

based in London, United Kingdom

Feb
2
reviewed Approve suggested edit on Did Italian irredentists ever lay claim to the Swiss Canton of Tessin?
Feb
1
awarded Good Question
Jan
31
awarded Popular Question
Jan
30
awarded Enlightened
Jan
30
awarded Nice Answer
Jan
29
awarded Supporter
Jan
29
awarded Autobiographer
Jan
28
awarded Popular Question
Jan
28
awarded Nice Answer
Jan
25
awarded Good Answer
Jan
25
awarded Popular Question
Jan
24
awarded Good Answer
Jan
19
comment Constructive proof of the Halting Problem
@Kaveh: Sure, I'm with you there. It's my "side-question" that I'm still unsure about: where does diagonalisation come into it at all? I don't see any need for it in the proof.
Jan
18
comment Constructive proof of the Halting Problem
@Kaveh: There's no confusion about diagonalisation being non-constructive. Please reread my question; the issue of diagonalisation is separate.
Jan
18
comment Constructive proof of the Halting Problem
@jozefg: Thanks, I'm starting to see you're right. There's one other point though. (Are you familiar with the proof in Sipser?) It seems like the use of the diagonal argument is very artificial and not in fact needed at all. Does it actually have a genuine place in the proof, or other reasoning connected to the halting problem?
Jan
18
comment Constructive proof of the Halting Problem
@jozefg: The question now is: where exactly in the common proof is LEM used? Hmm.
Jan
18
comment Constructive proof of the Halting Problem
Down-voters care to explain??
Jan
18
comment Constructive proof of the Halting Problem
@jozefg: Yeah, that's quite true: the lack of LEM (for that predicate) seems to be the real problem here. The 'proof by contradiction' is on second thought a benign one.
Jan
18
comment Constructive proof of the Halting Problem
@jozefg: Possibly both. I kind of brushed over that issue of LEM, since it's possible that a restricted form of LEM applies to the predicate "TM does halt" (though I'm not at all sure on this).
Jan
18
comment Constructive proof of the Halting Problem
@HuckBennett But he doesn't, he uses diagonalisation as an afterthought to the proof...
1 2 3 4 5