Ask HN: Can all of 32bit computing fit within a single 16GB permutation of 2^32?
And am I correct in intuiting that computing over the permutation would be NP-Complete?
The idea is that since technically all 32 bit opcodes, data representations, and encoding instructions(Unicode text, 24 bit color/audio) for computers come down to byte-sized combinations of bits (yes, there's nibbles and words and half-words too)--and these are necessarily limited to <2^32--, that any combination of bits used to represent an opcode or data are stored within the permutation, eliminating the need to store data beyond the 16GB partition.
Every bit pattern needed to move to another bit pattern is contained within the permutation.
This horrible Hello World bit bang I did on an 8bit CPU I made up is contained within the permutation, and could conceivably run against a virtualization of the CPU which would also be contained within the permutation if it were virtualized on a 32bit system.
0b00000011 0b10000110 0b00100000 0b10000010 0b00101000 0b10000001 0b01000100 0b10011100 0b10100110 0b00100101 0b10000001 0b01000100 0b10011001 0b01000100 0b10011100 0b10100110 0b00100110 0b10000001 0b01000110 0b10011001 0b01000100 0b10011100 0b10100110 0b10100110 0b00101111 0b10000001 0b01000100 0b10011001 0b01000100 0b10011100 0b10100110 0b00100000 0b10000100 0b10100110 0b00010111 0b10000001 0b01000100 0b10011001 0b01000100 0b10011100 0b10100110 0b00101111 0b10000001 0b01000100 0b10011001 0b01000100 0b10011100 0b10100110 0b00110010 0b10000001 0b01000100 0b10011001 0b01000100 0b10011100 0b10100110 0b00100110 0b10000001 0b01000110 0b10011001 0b01000100 0b10011100 0b10100110 0b00100100 0b10000001 0b01000100 0b10011001 0b01000100 0b10011100 0b10100110 0b00100001 0b10000100 0b10100110
The permutation, being a tape of 1s and 0s could then be acted upon by a multi-state machine to reproduce the actions necessary to play an audio file or execute a program without any additional data storage.
Has this been theorized before? Is it the sort of thing that is so obvious that it's taken for granted and not worth discussion? Is the NP-hardness of it so astronomical only the insane could and would conceive of such a folly?
Not the Turing Machine bit, obviously, but that all representations of data and program execution for any 32 bit system are necessarily contained within a permutation of the 32bit space?
My intuition about it being NP-hard or NP-Complete is that it seems, thinking briefly about it, that you would need to know ahead of time which pattern jumps to the next pattern which reprents your data or instruction and also jumps to the next next pattern so on such that to derive the starting pattern you need to follow all possible patterns from the destination pattern back to the starting pattern for all possible actions taken. At that point we're just solving the halting problem the hard way, aren't we?
I won't directly answer your questions but consider this. We have a function F that accepts an argument of size N and returns the result after N² instructions. Its time complexity is O(N²).
Now consider F'. F' is like F but we limit N to a fixed constant -- for example we say that N must be ≤ 2³². In this case, _for every input_ F' returns the result after at most (2³²)² = 2⁶⁴ instructions. Its time complexity is O(1). Note that O(2⁶⁴) = O(2⁶⁴ * 1) = O(1).
---
Technically, all implementable-on-real-machines algorithms either return after O(1) instructions, or loop after O(1) instructions. But being O(1) doesn't imply being fast in practice.
You might be also interested in reading about galactic algorithms: https://en.wikipedia.org/wiki/Galactic_algorithm.