4 ms·

In case anyone wants a quick tl;dr: as the length of a program (expressed as the number of states in a Turing machine) grows, the relative fraction of undecidab

by dgacmu 3y ago

In case anyone wants a quick tl;dr: as the length of a program (expressed as the number of states in a Turing machine) grows, the relative fraction of undecidable programs decreases. In other words, "most" (approaching "nearly all" as they get longer) Turing machines, out of the set of all possible Turing machines of that same size, are actually decidable. (Though this doesn't tell us about whether most real programs are decidable, as the programs humans write also come from a small subset of the universe of Turing machines. But we know that in practice, this is also true). This relates nicely to the earlier discussion of SAT: while SAT is NP-complete, many instances can be solved in reasonable time. Similarly, we can verify that many actual programs will halt even if the problem is, in general, undecidable.

bawolff 3y ago
I think it would be pretty shocking if the opposite were true. I imagine most randomly generated turing machines are pretty trivial.
- mananaysiempre 3y ago
  Dunno. The real numbers, for example, are in the “most things are eldritch abominations” camp[1]: the reals are uncountable, the computable reals are a(n everywhere dense) countable set[2] (that is therefore[3]) of measure zero. Not that there’s a reason to expect these cases to be similar, just that weird things do happen. [1] https://mathwithbaddrawings.com/2016/12/28/why-the-number-line-freaks-me-out/ https://mathwithbaddrawings.com/2016/12/28/why-the-number-li... [2] There’s a finite set of programs of a fixed length, thus (countable union of finite sets) a countable set of all programs, thus only at most a countable set of numbers they can compute. [3] Every countable set has Lebesgue measure zero: cover point #n by a blot of measure ε / 2^n (that could even intersect other blots) to prove all of them have measure at most ε > 0, take ε as small as desired.
  - orlp 3y ago
    I've made the argument many times before that the reals are certainly an interesting set of objects, but a poor abstraction for the concept of a number. We should work towards replacing them with a more well-behaved set without eldritch monsters such as uncomputable 'numbers' that you can't add or multiply with. E.g. https://en.wikipedia.org/wiki/Computable_number https://en.wikipedia.org/wiki/Computable_number.
    - zeroonetwothree 3y ago
      Computable functions do also have some weird behavior. For example: a) all functions are continuous, b) equality is not computable (maybe not so weird for anyone used to floating point), c) differentiation is not computable unless you work over complex numbers (but integration is!)
      - orlp 3y ago
        a) All functions from computable reals to computable reals are continuous. This makes sense, because an arbitrarily small input difference leading to an arbitrarily large output difference is not a good basis for computation. You can still have discontinuities for discrete computable maps. b) Neither is equality computable for the reals. Nothing is lost here. c) Differentiation is computable for the functions of computable reals if you have a computable rate of convergence.
        chromoblob 3y ago
        How to do (c)? I tried to model the reals as lazily computed sequences of intervals with rational bounds where every next interval is subset of previous one, and couldn't write a higher-order differentiator function because on every step for a given input interval there is output interval with non-zero (in most cases) size and the differentiated function may contain quick enough oscillations that the derivative is unbounded, and thus the derivative will stay unbounded no matter what you do. What do you mean by rate of convergence?
        3y ago
  - passion__desire 3y ago
    tl;dr : Maybe the reals are far more mysterious. All we ever have handle over are the countable sets. [0] Looking back, the core of my confusion was this. I had thought: I can visualize what ℵ0 means; that’s just the infinity of integers. I can also visualize what C=2^ℵ0 means; that’s the infinity of points on a line. Those, therefore, are the two bedrocks of clarity in this discussion. By contrast, I can’t visualize a set of intermediate cardinality between ℵ0 and C. The intermediate infinity, being weird and ghostlike, is the one that shouldn’t exist unless we deliberately “force” it to. Turns out I had things backwards. For starters, I can’t visualize the uncountable infinity of real numbers. I might think I’m visualizing the real line—it’s solid, it’s black, it’s got little points everywhere—but how can I be sure that I’m not merely visualizing the ℵ0 rationals, or (say) the computable or definable reals, which include all the ones that arise in ordinary math? The continuum C is not at all the bedrock of clarity that I’d thought it was. Unlike its junior partner ℵ0, the continuum is adjustable, changeable—and we will change it when we build different models of ZFC. What’s (relatively) more “fixed” in this game is something that I, like many non-experts, had always given short shrift to: Cantor’s sequence of Alephs ℵ0, ℵ1, ℵ2, etc. [0] https://scottaaronson.blog/?p=4974 https://scottaaronson.blog/?p=4974
  - _0w8t 3y ago
    The notion of uncountable set assumes certain axioms and classical logic. If instead one assumes rules of constructive mathematics, then one cannot construct uncountable set. Simplifying only computable numbers can exist.
    - mananaysiempre 3y ago
      Note that there are multiple versions[1] of “constructive mathematics”, so for example what Bishop’s constructive real analysis book considers constructive is not what Markov’s “constructive = computable” tradition does. You are also going to encounter other funny things. One of De Morgan’s laws failing could seem troubling but ultimately theoretical—how, then, about the distinction about countable and constructively countable[3]? The set of all programs is countable; the set of all terminating programs is a subset of it, but can’t constructively be proven to itself be countable—after all, that would imply a solution to the halting problem! (Neither can it constructively be proven to not be such, as it is such in a consistent extension, namely classical mathematics.) Thus you get the new and exciting notion of subcountable sets. And that’s one of the mildest things that you’re going to encounter in your shiny new theory of cardinals. (Anybody who can explain to me what the hell constructive Hahn—Banach[4] is about gets a beverage of their choice if we are ever in the same city. Without HB, you cannot do any functional analysis worth a damn, and without that you can’t really talk about Green’s functions / fundamental solutions to linear PDEs, which are in turn a basic tool for any electodynamics or quantum mechanics worth speaking about. Unless you want to forgo proof or the natural sciences, you need it, is my point.) None of this is to say that I think intuitionistic logic is useless, mind you. It’s interesting and useful[5]! But so far it seems that you need to learn at least some logic (as a piece of mathematics and not mere terminology, so including scary words like “metalogic”) before you can really understand how it comes together. [1] It seems categorical logic[2] says useful things about what the One True Definition should be? But I don’t understand it well enough to tell, and in any case the constructivist tradition predates not only it but category theory in general. [2] https://mikeshulman.github.io/catlog/catlog.pdf https://mikeshulman.github.io/catlog/catlog.pdf [3] https://ncatlab.org/nlab/show/constructive+mathematics https://ncatlab.org/nlab/show/constructive+mathematics [4] https://www.cse.chalmers.se/~coquand/hahn1.pdf https://www.cse.chalmers.se/~coquand/hahn1.pdf [5] https://www.ams.org/journals/bull/2017-54-03/S0273-0979-2016-01556-4/S0273-0979-2016-01556-4.pdf https://www.ams.org/journals/bull/2017-54-03/S0273-0979-2016...
- EscapeFromNY 3y ago
  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.
EGreg 3y ago
Also the same applies with the CAP theorem… it is mostly a theoretical result but in practice things go well the vast majority of the time! Also look up Buridan’s Principle by Leslie Lamport. I emailed him and “argued” with him for a while after reading his paper, but in a theoretical sense and some practical subsets it is correct!
- sebzim4500 3y ago
  Interesting paper. I agree that he is probably technically correct, but I think he downplays the fact that all over physics people say "never" when they mean "with probably less than 10^-1000. For example, in classical thermodynamics there is a nonzero probability that all the air molecules in a room will happen to travel to one side, violating many laws of fluid mechanics. In quantum mechanics the situation is even worse, where basically anything can happen with nonzero probability.
  - galaxyLogic 3y ago
    > basically anything can happen with nonzero probability. It took me some time to realize that that's what "HitchHiker's Guide to Galaxy" was about.
SilasX 3y ago
I’m not sure the comparison to SAT is a good one because, in that case, we know of particular “phase transition” regions in which most problems aren’t clearly satisfiable or unsatisfiable. (Specifically, when the ratio of clauses to variables in 3SAT is about 4.2.)
- oldgradstudent 3y ago
  It's an excellent comparison to SAT, because in both cases nobody cares about random instances at all. For non-random instances the ratio of clauses to variables in is utterly meaningless.
zeroonetwothree 3y ago
The simplex algorithm is similar being exponential time worst case but in practice often closer to linear
turminal 3y ago
The difference with SAT is that for SAT we actually know the opposite is true - the instances that can be solved quickly are the "rare" kind.

by dgacmu 3y ago

bawolff 3y ago

I think it would be pretty shocking if the opposite were true. I imagine most randomly generated turing machines are pretty trivial.

mananaysiempre 3y ago
Dunno. The real numbers, for example, are in the “most things are eldritch abominations” camp[1]: the reals are uncountable, the computable reals are a(n everywhere dense) countable set[2] (that is therefore[3]) of measure zero. Not that there’s a reason to expect these cases to be similar, just that weird things do happen. [1] https://mathwithbaddrawings.com/2016/12/28/why-the-number-line-freaks-me-out/ https://mathwithbaddrawings.com/2016/12/28/why-the-number-li... [2] There’s a finite set of programs of a fixed length, thus (countable union of finite sets) a countable set of all programs, thus only at most a countable set of numbers they can compute. [3] Every countable set has Lebesgue measure zero: cover point #n by a blot of measure ε / 2^n (that could even intersect other blots) to prove all of them have measure at most ε > 0, take ε as small as desired.
- orlp 3y ago
  I've made the argument many times before that the reals are certainly an interesting set of objects, but a poor abstraction for the concept of a number. We should work towards replacing them with a more well-behaved set without eldritch monsters such as uncomputable 'numbers' that you can't add or multiply with. E.g. https://en.wikipedia.org/wiki/Computable_number https://en.wikipedia.org/wiki/Computable_number.
  - zeroonetwothree 3y ago
    Computable functions do also have some weird behavior. For example: a) all functions are continuous, b) equality is not computable (maybe not so weird for anyone used to floating point), c) differentiation is not computable unless you work over complex numbers (but integration is!)
    - orlp 3y ago
      a) All functions from computable reals to computable reals are continuous. This makes sense, because an arbitrarily small input difference leading to an arbitrarily large output difference is not a good basis for computation. You can still have discontinuities for discrete computable maps. b) Neither is equality computable for the reals. Nothing is lost here. c) Differentiation is computable for the functions of computable reals if you have a computable rate of convergence.
      - chromoblob 3y ago
        How to do (c)? I tried to model the reals as lazily computed sequences of intervals with rational bounds where every next interval is subset of previous one, and couldn't write a higher-order differentiator function because on every step for a given input interval there is output interval with non-zero (in most cases) size and the differentiated function may contain quick enough oscillations that the derivative is unbounded, and thus the derivative will stay unbounded no matter what you do. What do you mean by rate of convergence?
        3y ago
- passion__desire 3y ago
  tl;dr : Maybe the reals are far more mysterious. All we ever have handle over are the countable sets. [0] Looking back, the core of my confusion was this. I had thought: I can visualize what ℵ0 means; that’s just the infinity of integers. I can also visualize what C=2^ℵ0 means; that’s the infinity of points on a line. Those, therefore, are the two bedrocks of clarity in this discussion. By contrast, I can’t visualize a set of intermediate cardinality between ℵ0 and C. The intermediate infinity, being weird and ghostlike, is the one that shouldn’t exist unless we deliberately “force” it to. Turns out I had things backwards. For starters, I can’t visualize the uncountable infinity of real numbers. I might think I’m visualizing the real line—it’s solid, it’s black, it’s got little points everywhere—but how can I be sure that I’m not merely visualizing the ℵ0 rationals, or (say) the computable or definable reals, which include all the ones that arise in ordinary math? The continuum C is not at all the bedrock of clarity that I’d thought it was. Unlike its junior partner ℵ0, the continuum is adjustable, changeable—and we will change it when we build different models of ZFC. What’s (relatively) more “fixed” in this game is something that I, like many non-experts, had always given short shrift to: Cantor’s sequence of Alephs ℵ0, ℵ1, ℵ2, etc. [0] https://scottaaronson.blog/?p=4974 https://scottaaronson.blog/?p=4974
- _0w8t 3y ago
  The notion of uncountable set assumes certain axioms and classical logic. If instead one assumes rules of constructive mathematics, then one cannot construct uncountable set. Simplifying only computable numbers can exist.
  - mananaysiempre 3y ago
    Note that there are multiple versions[1] of “constructive mathematics”, so for example what Bishop’s constructive real analysis book considers constructive is not what Markov’s “constructive = computable” tradition does. You are also going to encounter other funny things. One of De Morgan’s laws failing could seem troubling but ultimately theoretical—how, then, about the distinction about countable and constructively countable[3]? The set of all programs is countable; the set of all terminating programs is a subset of it, but can’t constructively be proven to itself be countable—after all, that would imply a solution to the halting problem! (Neither can it constructively be proven to not be such, as it is such in a consistent extension, namely classical mathematics.) Thus you get the new and exciting notion of subcountable sets. And that’s one of the mildest things that you’re going to encounter in your shiny new theory of cardinals. (Anybody who can explain to me what the hell constructive Hahn—Banach[4] is about gets a beverage of their choice if we are ever in the same city. Without HB, you cannot do any functional analysis worth a damn, and without that you can’t really talk about Green’s functions / fundamental solutions to linear PDEs, which are in turn a basic tool for any electodynamics or quantum mechanics worth speaking about. Unless you want to forgo proof or the natural sciences, you need it, is my point.) None of this is to say that I think intuitionistic logic is useless, mind you. It’s interesting and useful[5]! But so far it seems that you need to learn at least some logic (as a piece of mathematics and not mere terminology, so including scary words like “metalogic”) before you can really understand how it comes together. [1] It seems categorical logic[2] says useful things about what the One True Definition should be? But I don’t understand it well enough to tell, and in any case the constructivist tradition predates not only it but category theory in general. [2] https://mikeshulman.github.io/catlog/catlog.pdf https://mikeshulman.github.io/catlog/catlog.pdf [3] https://ncatlab.org/nlab/show/constructive+mathematics https://ncatlab.org/nlab/show/constructive+mathematics [4] https://www.cse.chalmers.se/~coquand/hahn1.pdf https://www.cse.chalmers.se/~coquand/hahn1.pdf [5] https://www.ams.org/journals/bull/2017-54-03/S0273-0979-2016-01556-4/S0273-0979-2016-01556-4.pdf https://www.ams.org/journals/bull/2017-54-03/S0273-0979-2016...
EscapeFromNY 3y ago
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.

EGreg 3y ago

Also the same applies with the CAP theorem… it is mostly a theoretical result but in practice things go well the vast majority of the time! Also look up Buridan’s Principle by Leslie Lamport. I emailed him and “argued” with him for a while after reading his paper, but in a theoretical sense and some practical subsets it is correct!

sebzim4500 3y ago
Interesting paper. I agree that he is probably technically correct, but I think he downplays the fact that all over physics people say "never" when they mean "with probably less than 10^-1000. For example, in classical thermodynamics there is a nonzero probability that all the air molecules in a room will happen to travel to one side, violating many laws of fluid mechanics. In quantum mechanics the situation is even worse, where basically anything can happen with nonzero probability.
- galaxyLogic 3y ago
  > basically anything can happen with nonzero probability. It took me some time to realize that that's what "HitchHiker's Guide to Galaxy" was about.

SilasX 3y ago

I’m not sure the comparison to SAT is a good one because, in that case, we know of particular “phase transition” regions in which most problems aren’t clearly satisfiable or unsatisfiable. (Specifically, when the ratio of clauses to variables in 3SAT is about 4.2.)

oldgradstudent 3y ago
It's an excellent comparison to SAT, because in both cases nobody cares about random instances at all. For non-random instances the ratio of clauses to variables in is utterly meaningless.

zeroonetwothree 3y ago

The simplex algorithm is similar being exponential time worst case but in practice often closer to linear

turminal 3y ago

The difference with SAT is that for SAT we actually know the opposite is true - the instances that can be solved quickly are the "rare" kind.