5 ms·

My intuition tells me the opposite. Suppose you have one undecidable statement, U, out of s possible statements. A random program of length n contains U at lea

My intuition tells me the opposite. Suppose you have one undecidable statement, U, out of s possible statements. A random program of length n contains U at least once with probability 1-(1-1/s)^n. If the program is of infinite length, it contains U with probability 1. So I would have thought the chances of undecidability increase as the program gets longer. Clearly my intuition is wrong, per the paper, but I don't think the result is immediately obvious.

zeroonetwothree 3y ago
A statement in a program can’t really be undecidable on its own. It’s the program that has that property.
- chromoblob 3y ago
  A statement is just a subprogram. Whether it can be decidable depends on whether a single program can be undecidable (and I can't see how that could be possible, undecidability is property of the problem - decision procedure on set of programs)
cyberax 3y ago
Think about it like this, there are infinitely many Turing machine state classes that are easily decidable. For example, a simple infinite loop or its equivalent. Most of these classes are also very trivial to construct, and require only a few "instructions". So if you make a random TM, it's almost guaranteed that it'll get eventually "trapped" in one of these easily decidable infinite loops.
- EscapeFromNY 3y ago
  Thanks, that's a perfect explanation
bawolff 3y ago
I think the chance of having an undecidable (group of) statements go up, but the chance of executing it does not. There isn't really a single undecidable statement, it would be a complex subroutine. My intuition would be its much more likely a halt or indef loop (both relatively simple) would appear before program control would transfer to the undecidable part, in most cases. I.e. if something undecidable requires 60 symbols in a row in correct order, but halting requires one, than probability of a halt at any given spot seems much higher on average.
CaptainNegative 3y ago
It entirely depends on the description language. In Python, the opposite is true for basically the reason you gave: an asymptotically positive constant fraction of valid Python programs will begin with code searching for a contradiction to ZFC followed by an exit statement. In the model where Turing machines are modeled by random graphs with out-degree two, it is no longer necessarily the case that the start state component is exactly some fixed undecidable subgraph; i.e. as more states are added the probability of finding the start state inside a particular induced subgraph shrinks to zero.

zeroonetwothree 3y ago

A statement in a program can’t really be undecidable on its own. It’s the program that has that property.

chromoblob 3y ago
A statement is just a subprogram. Whether it can be decidable depends on whether a single program can be undecidable (and I can't see how that could be possible, undecidability is property of the problem - decision procedure on set of programs)

cyberax 3y ago

Think about it like this, there are infinitely many Turing machine state classes that are easily decidable. For example, a simple infinite loop or its equivalent. Most of these classes are also very trivial to construct, and require only a few "instructions". So if you make a random TM, it's almost guaranteed that it'll get eventually "trapped" in one of these easily decidable infinite loops.

EscapeFromNY 3y ago
Thanks, that's a perfect explanation

bawolff 3y ago

I think the chance of having an undecidable (group of) statements go up, but the chance of executing it does not. There isn't really a single undecidable statement, it would be a complex subroutine. My intuition would be its much more likely a halt or indef loop (both relatively simple) would appear before program control would transfer to the undecidable part, in most cases. I.e. if something undecidable requires 60 symbols in a row in correct order, but halting requires one, than probability of a halt at any given spot seems much higher on average.

CaptainNegative 3y ago

It entirely depends on the description language. In Python, the opposite is true for basically the reason you gave: an asymptotically positive constant fraction of valid Python programs will begin with code searching for a contradiction to ZFC followed by an exit statement. In the model where Turing machines are modeled by random graphs with out-degree two, it is no longer necessarily the case that the start state component is exactly some fixed undecidable subgraph; i.e. as more states are added the probability of finding the start state inside a particular induced subgraph shrinks to zero.