News for hackers. Stuff that matters.

A comment on Cities: Skylines Is Turing Complete. Parent comment

Re:Cities: Skylines Is Turing Complete by mys_721tx on Monday July 15, 2019 @10:29PM (#20447036)
Turing machine has unbounded memory. There is a difference between unbounded and unlimited memory: You can extend the tape as needed, but at any given step of computation, the used space is finite.

A Turing machine with bounded memory is called linear bounded automaton. Although LBA is less powerful than a Turing machine in the absolute sense, it is not trivial to form a problem that a Turing machine could decide but a LBA could not.

[ Parent | on HN ]
Re:Cities: Skylines Is Turing Complete by ignaloidas on Tuesday July 16, 2019 @03:30AM (#20448167)
The difference is that with LBA you can determine if the program will end or not, as you can check all of the finite states it can have.
[ Parent | on HN ]