Timeline for Finding the largest integer describable with a string of symbols of predefined length
Current License: CC BY-SA 4.0
9 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| S Jul 18 at 4:33 | history | suggested | Lucenaposition | CC BY-SA 4.0 |
fixed typo
|
| Jul 18 at 3:31 | review | Suggested edits | |||
| S Jul 18 at 4:33 | |||||
| Apr 13, 2011 at 13:38 | vote | accept | Jose Brox | ||
| Jul 27, 2010 at 1:25 | comment | added | Joel David Hamkins | Both of my remarks should be tempered by the observation that if you really inist on the 3x5 limitation, then there are after all only finitely many things to write, and if each has an answer, then the outcomes will in fact be computable for this reason. What my arguments show is that there is no uniform method (uniform in the size of the card) of determining the winner. | |
| Jul 27, 2010 at 1:20 | history | edited | Joel David Hamkins | CC BY-SA 2.5 |
Added second remark
|
| Jul 22, 2010 at 11:52 | comment | added | Joel David Hamkins | If there were a program $S$ that determined whether the $n^{\rm th}$ program gave output $n$ on input $n$, then let $T$ be the program that on input $n$, consults $S$ to check if $n$ is a program that outputs $n$ on $n$, if so, output $n+1$, otherwise, output $n$. If $T$ is program number $t$, then $T$ gives output $t+1$ on $t$ if and only if it gives output $t$, a contradiction. This implies the incompleteness theorem, since it shows that you can't prove all instances of the "otherwise" case, for if you could then you could build such an $S$. | |
| Jul 22, 2010 at 5:17 | comment | added | Will Jagy | Thank you, Joel. I did not realize quite how good a teacher Spencer was at the time. He moved to Courant after I left for graduate school, I guess he is still there. Same with Jeff Cheeger. | |
| Jul 22, 2010 at 4:20 | comment | added | Will Jagy | Joel Spencer asked us the three by five card question on about the first day of the class in logic. This would have been about 1977 at Stony Brook. He also gave this neat proof of Incompleteness, number all computer programs that output a single number, ask whether there is a superprogram S that decides "Does program number n output n?" then derive a contradiction because S also has a number and...I forget what happens next but it was short and convincing. | |
| Jul 22, 2010 at 4:06 | history | answered | Joel David Hamkins | CC BY-SA 2.5 |