Turing-complete for the wrong reasons

Collection of things that are obviously Turing-complete, but not for the reasons you expect

Old ECMAScript

If you were to implement a Turing-tape in JS, which data-type or structure would you choose?

• Array<boolean>
• string
• bigint
• Map<number, boolean>

If your answer is array or string, you've lost because max array.length is 2**32-1 and max string.length is 2**53-1, so you can't (theoretically) simulate a Turing-machine.

If you choose a Map keyed by number, you also lose because there's only ~2**63 unique Float64s.

If you choose bigint, you won! ECMAScript, defines no bounds on the value or size of a BigInt.

But what if we were on an early version of ES? There's no Map, no bigint, no Set... what else could we use to get unbounded memory?

Enter the humble Object. An Object can theoretically hold any number of keys, so use an object like this:

{"-1": false,"0": true, "1": false}

Is enough to get infinite memory! problem solved! right?

No. That gives you ~2^(2^53-1). A mind-numbing size of memory, but still finite. And you can't use Symbols because they didn't exist back then.

The real solution is not a flat object, it's a nested object. By using objects as a tree, you can artificially expand the number of unique keys you can use, granting unbounded memory!