Hacker News Reader

It can be solved if the memory is bounded. But unbounded memory comes with undecidable problems.

This truly leads into "computation"; when we're dealing with known quantities, yes, we can "solve" the halting problem. The second you move into "we don't know the answer yet", the can of worms opens. Thank you.

Computation is the study of infinity. That is how I like to think about it. It doesn't seem that way when you're building a website (well, in some ways because it's not at that point), but every algorithm, data structure, etc is an investigation into a certain part of infinity. Think of the way in which we generally categorize algorithms (Big-O notation)... that's just characterizing infinity.

There remain undecidable problems even with finite memory/state space.

Linear bounded automata (LBA) the halting problem is decidable. But many properties of LBA are undecidable:

Emptiness: Does an LBA reject all possible inputs? Universality: Does an LBA accept all possible inputs over its alphabet? Equivalent: Do two LBA accept the same language? Finiteness: Does an LBA accept a finite number of strings.

Reply on news.ycombinator.com