I want to post a challenge using only Turing Machines. I want the winning solution to be a combination of smallest machine (fewest states) and shortest worst case runtime (up to two machines). I am unsure how to score this. A penalty would be added to the score for having two machines. The challenge will be to run the machine over variably sized data until the exit condition is met, so the same machine needs to be able to cope with both small data and large data.
- Size of machine - easy: a 5-state machine beats a 7-state machine
- Runtime - hard
If the data is size $x$ how would I score a time of $x^2$ vs $x+10000$? The first one is $O(x^2)$ but the second one is $O(x)$ even though it will only win when the data is larger than 100. Also, how could I provide rules for condensing this into a single number so people could score their own answer?
Should I just limit it to size?
I just realised that if I do allow two machines, one for size, one for speed, that I want to weight their scores evenly. I don't want people to favour one or the other just because they can score better that way! They should be trying for the smallest and fastest single machine, if possible.
I am now considering multiplying the size of the smallest machine by the runtime of the largest machine. For one machine this is just size x time.