Shufflepants wrote:Code: Select all

` check to see if what the machine has produced on its tape is the sorted list, if it is return it`

I love how the fastest algorithms for checking set equality of both lists involve... sorting both lists.

About the upper bound of the runtime complexity. Enumerating a turing machine by some bitwise encoding is great for saying that you have 2^n turing machines with n bits, but that doesn't help us in figuring out what these turing machines can do.

So I'll be using a turing machine defined by 5-tuples: (state, symbol, new symbol, new state or terminate, tape movement), and we will iterate by the amount of tuples required to define the machine.

How many machines with t tuples are there? There's at most as many states as tuples, there are exactly n symbols, and tape movement is (left, hold, right), so we have t^2 * n * (n+1) * 3 possible tuples on a t-tuple machine with n symbols, thus:

s(t, n) := (t^2 * n * (n+1) * 3) ^ t possible machines with t tuples over n symbols.

^{1}With this definition, for a list of n elements, there is a trivial turing machine with n tuples that outputs a permutation of that list after n steps, like this:

(1, *, 1, 2, right)

(2, *, 2, 3, right)

...

(n, *, n, terminate, hold)

where * is whatever symbol the empty tape contains.

In other words, after having executed n steps on any turing machine with n tuples, the algorithm must have terminated.

Now we can calculate how many machines get instantiated before our trivial winner is found:

sum(i from 1 to n) (i^2*n^2)^i

Add n iterations to actually run the machine, figure out that the whole loop requires O(n^2) for n iterations

^{2}, so in theory we have everything we need to establish an upper bound.

Eyeballing the thing seems to lead to something like O(n^n), so you might actually have created something worse than O(n!).

^{1} Many of those machines will have unreachable states, and we might find a more efficient iteration, but we're interested in an upper bound.

^{2} Assuming no turing machine is ever removed from the list, though I would be surprised if removal of the terminated machines would lower the complexity class. If you actually have a useful bound on the fraction of turing machines that terminate after a set amount of steps, I have a suspicion that you've gotten terribly close to computing the non-computable busy beaver numbers.