4 ms·
People keep forgetting you need infinite memory to be Turing complete. On a machine with finite memory, all operations are O(1).
by blamestross 5y ago
People keep forgetting you need infinite memory to be Turing complete. On a machine with finite memory, all operations are O(1).
- k__ 5y agoAll operations are O(1)?
- blamestross 5y agobusy beaver function of (a finite number) is hilariously big, but a constant. So there is a constant bound on the duration of all terminating programs using finite memory.
- tomcatfish 5y agoAlmost, but there are examples of non-termination still unless I am misremembering a definition (ex 20 GOTO 10).