Comment on Is my cat Turing-complete?parentComments−blamestross4yPeople keep forgetting you need infinite memory to be Turing complete. On a machine with finite memory, all operations are O(1).−tomcatfish4yAlmost, but there are examples of non-termination still unless I am misremembering a definition (ex 20 GOTO 10).−k__4yAll operations are O(1)?−blamestross4ybusy 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.
Comments
People keep forgetting you need infinite memory to be Turing complete. On a machine with finite memory, all operations are O(1).
Almost, but there are examples of non-termination still unless I am misremembering a definition (ex 20 GOTO 10).
All operations are O(1)?
busy 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.