On Monday, 29 July 2013 at 12:36:36 UTC, John Colvin wrote:

On Monday, 29 July 2013 at 12:35:59 UTC, John Colvin wrote:On Monday, 29 July 2013 at 12:17:22 UTC, JS wrote:Even something like## Advertising

for(;;) { if (random() == 3) break; } is decidable(it will halt after some time).That program has a finite average runtime, but its maximumruntime is unbounded. You can't actually say it *will* halt.For any given input (in this case 0 inputs) one cannot tellwhether the program will eventually halt, therefore it isundecidable.I have formal background in CS so I might have got thattotally wrong.sorry, that should be "I have NO formal background in CS"

No, again, it isn't about infinite run time. decidability != infinite run time. to simplify, let's look at the program, for(;;) if (random() == 0) break;

`where random() returns a random number, not necessarily uniform,`

`between 0 and 1.`

Same problem just easier to see.

`Since there must be a chance for 0 to occur, the program must`

`halt, regardless of how long it takes, even if it takes an`

`"infinite" amount of time.`

`That is, the run time of the program may approach infinity BUT it`

`will halt at some point because by the definition of random, 0`

`must occur... else it's not random.`

`So, by the fact that random, must cover the entire range, even if`

`it takes it an infinitely long time(so to speak), we know that`

`the program must halt. We don't care how long it will take but`

`just that we can decide that it will.`

`The only way you could be right is if random wasn't random and 0`

`was never returned... in that case the program would not halt...`

`BUT then we could decide that it never would halt...`

`In both cases, we can decide the outcome... if random is known to`

`produce 0 then it will halt, if it can't... then it won't.`

`But random must produce a 0 or not a 0 in an infinite amount of`

`time. (either 0 is in the range of random or not).`

`That is, the halting state of the program is not random even`

`though it looks like it. (again, it's not how long it takes but`

`if we can decide the outcome... which, in this case, rests on the`

`decidability of random)`

`Another way to see this, flipping a fair coin has 0 probability`

`of producing an infinite series of tails.`

Why?

`After N flips, the probability of flipping exactly N tails is 1/N`

`-> 0.`