Hacker News new | past | comments | ask | show | jobs | submit login

a Turing machine has an infinite tape. a typical computer has finite memory. therefore, it's tape is upper bounded by a constant function. this is a kind of linear bounded automata: http://en.wikipedia.org/wiki/Linear_bounded_automata

linear bounded automata don't have a halting problem. it's perfectly decidable. this doesn't detract from the fact it may take a long time to decide, but it is a far easier problem than halting on a TM.




The Javascript spec probably doesn't specify a fixed memory limit, so limiting the space arbitrarily to X mb is not that different from limiting the time arbitrarily to Y s.


Except verifying termination with a bound in the seconds of computation can be done in O(n), where n is the maximum number of seconds allowed (you can see that trivially by just waiting n seconds and killing the program if it doesn't terminate). On the other hand, if you try to limit a program's memory usage, it can take up to O(2^n) time to detect that a program with budget of n bits terminates (it might seem easier than that, but the program can go into an infinite loop without overflowing memory, like "while (1) {}"). You must consider that such a program can never have more than one state for each possible configuration of its allowed memory space (which is 2^n) and you can tell that it is in and infinite loop only when it repeats a previously used state. To do that correctly, then, takes a long time.

Incidentally, this is why PSPACE (the class of decision problem decidable in a turing machine with polynomially limited space) seems a lot more powerful than P (the set of decision problems decidable using a polynomial amount of time).




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: