Timeline for Are there any proofs the undecidability of the halting problem that does not depend on self-referencing or diagonalization ?
Current License: CC BY-SA 2.5
9 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Dec 16, 2010 at 22:44 | comment | added | user1338 | Hmmm...are you sure? I might be confused about what exactly the definition of "diagonalization" is. I had read that Boolos claimed that he had given a proof of Godel's Incompleteness theorems that didn't use diagonalization by using the Berry paradox. Anyway, if this is diagonalization, what is the diagonal? I agree that they proof may be relativizizing, but I had thought that to qualify as actual diagonalization you would have to use different logic. | |
| Dec 16, 2010 at 22:36 | comment | added | Mark Reitblatt | @Philip you are diagonalizing on $f$, it's just a different $f$ from the classical proof | |
| Dec 16, 2010 at 22:04 | comment | added | user1338 | @Mark Reitblatt: Thank you, I've made the correction. | |
| Dec 16, 2010 at 22:04 | history | edited | user1338 | CC BY-SA 2.5 |
added 19 characters in body
|
| Dec 16, 2010 at 22:01 | comment | added | Mark Reitblatt | @Philip Minor technical correction: you should change integer to natural or positive integer. | |
| Dec 16, 2010 at 22:00 | comment | added | Mark Reitblatt | @johne I concur with Philip. There is no assumption on the limits of the machine's representation. This is a TM. | |
| Dec 16, 2010 at 19:48 | comment | added | user1338 | I'm not trying to be rude, but your objection makes no sense. The function f is defined as a function that outputs an integer that can't be computed by M on any input with length less than n. Thus, nonsensical appeals to modular arithmetic aside, you're going to have a difficult time showing that the sentence you highlighted is invalid. | |
| Dec 16, 2010 at 19:03 | comment | added | johne |
This proof is invalid. Whatever it outputs, it ought to be an integer that is not computable by the machine computing f on input I with length less than that given. An appeal to modular arithmetic shows this to be trivially false. The error is in assuming the machine must be capable of representing $>n$ sized numbers in order to be able to perform arithmetic on them when in fact it is possible to perform arithmetic modulo $n$.
|
|
| Nov 12, 2010 at 4:51 | history | answered | user1338 | CC BY-SA 2.5 |