Re:Why Philosophers Should Care About Computational Complexi...
by whatshisface on Saturday July 21, 2018 @08:57AM
(#17581820)
If there was an algorithm that produced the busy beaver for a computer of a certian size, you could run it to see how long it would run and then compute the busy beaver function. The busy beaver function grows faster than any computable function[] so that's not possible.
Re:Why Philosophers Should Care About Computational Complexi...
by daveFNbuck on Saturday July 21, 2018 @10:19AM
(#17582064)
You couldn't use that to compute the busy beaver function, as the busy beaver function asks about Turing machines which have unlimited tape. You can solve it if you have a finite amount of tape, but you'd never know whether one of machines that tried to exceed the limit would have produced a longer output before eventually halting.
Now, this is a hunch based on research I have been working on: I believe that the programs that iterate the most states before halting have symmetry in time. The structure would mimic V [1]
Heres how the programs would operate: Iterate all possible configurations for a finite subset of the memory.
Then iterate all possible ways to iterate.
Then iterate all possible ways to iterate all possible ways.
In writing the program, one would repeat the nesting until the program's memory requirements cannot support a halting condition. And then dial it back until they do.
The naive procedural method of a bunch of nested for loops will fail spectacularly. Static code is simply an inefficient use of memory space. That is what makes the challenge to write this necessarily polymorphic/self-modifying emulation of V in time and memory, a challenge still unsolved. But I think we are close.
The amount of nesting would be a measure of the memory requirements necessary to iterate X configurations, a kind of constant representating the languages specific relationship between code and data, efficiency of sorts. This constant would be determined by the language but moreso, the limits of computation in general.
[1] https://en.wikipedia.org/wiki/Von_Neumann_universe