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 iterations2
, 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.