4 ms·

No one talks about the fact that the halting problem has been solved for linear bounded automata.

russdill 3y ago
Because it's immediately obvious that for anything with a finite number of states determining if it runs forever is "trivial" as running it until it either repeats a state or halts which will always occur in finite time.
- adamnemecek 3y ago
  Right, why are there so few total languages then?
  - reuben364 3y ago
    BRB, implementing a x86 interpreter with O(2^n) memory overhead.
    - adamnemecek 3y ago
      That's the brute force approach.
      - reuben364 3y ago
        I guess the alternative is just bounding the number of instructions and proving inside or outside your language that it is sufficient for your program.
        adamnemecek 3y ago
        Indeed, that's what bounded means.
        reuben364 3y ago
        Yes, but the point is that you are giving a constructive existence proof for that bound. You asked for why there are so few total languages. The answer, as far as I'm aware, is either brute force on a fixed amount of memory or giving provable bounds either by decision procedure on a restricted language or having to manually give a proof on a more expressive language. Is that that an answer to your (presumably rhetorical) question?
- amelius 3y ago
  Uh, yeah, but my PC with 96GB of memory has quite some possible states. So, most likely, the real reason nobody is interested is that the numbers are too large.
  - adamnemecek 3y ago
    Well the trick is knowing which states to keep track of.
  - russdill 3y ago
    If your computer had 4k of memory, it'd be too many states to keep track of
seanhunter 3y ago
When you say no one talks about it, isn't that what Turing means when he says: The fallacy in this argument lies in the assumption that Beta is computable. It would be true if we could enumerate the computable sequences by finite means, but the problem of enumerating computable sequences is equivalent to the problem of finding out whether a given number is the D.N of a circle-free machine, and we have no general process for doing this in a finite number of steps.[1] In an LBA can't we always enumerate the computable sequences by finite means? [1] On computable numbers https://www.cs.virginia.edu/~robins/Turing_Paper_1936.pdf https://www.cs.virginia.edu/~robins/Turing_Paper_1936.pdf

Because it's immediately obvious that for anything with a finite number of states determining if it runs forever is "trivial" as running it until it either repeats a state or halts which will always occur in finite time.

adamnemecek 3y ago
Right, why are there so few total languages then?
- reuben364 3y ago
  BRB, implementing a x86 interpreter with O(2^n) memory overhead.
  - adamnemecek 3y ago
    That's the brute force approach.
    - reuben364 3y ago
      I guess the alternative is just bounding the number of instructions and proving inside or outside your language that it is sufficient for your program.
      - adamnemecek 3y ago
        Indeed, that's what bounded means.
        reuben364 3y ago
        Yes, but the point is that you are giving a constructive existence proof for that bound. You asked for why there are so few total languages. The answer, as far as I'm aware, is either brute force on a fixed amount of memory or giving provable bounds either by decision procedure on a restricted language or having to manually give a proof on a more expressive language. Is that that an answer to your (presumably rhetorical) question?
amelius 3y ago
Uh, yeah, but my PC with 96GB of memory has quite some possible states. So, most likely, the real reason nobody is interested is that the numbers are too large.
- adamnemecek 3y ago
  Well the trick is knowing which states to keep track of.
- russdill 3y ago
  If your computer had 4k of memory, it'd be too many states to keep track of

seanhunter 3y ago

When you say no one talks about it, isn't that what Turing means when he says: The fallacy in this argument lies in the assumption that Beta is computable. It would be true if we could enumerate the computable sequences by finite means, but the problem of enumerating computable sequences is equivalent to the problem of finding out whether a given number is the D.N of a circle-free machine, and we have no general process for doing this in a finite number of steps.[1] In an LBA can't we always enumerate the computable sequences by finite means? [1] On computable numbers https://www.cs.virginia.edu/~robins/Turing_Paper_1936.pdf https://www.cs.virginia.edu/~robins/Turing_Paper_1936.pdf