Hacker News Reader

Comment by adamnemecek | Hacker News Reader

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

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.

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.

Well the trick is knowing which states to keep track of.

If your computer had 4k of memory, it'd be too many states to keep track of

Right, why are there so few total languages then?

BRB, implementing a x86 interpreter with O(2^n) memory overhead.

That's the brute force approach.

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.

Indeed, that's what bounded means.

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?

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

Reply on news.ycombinator.com