Turing Machine challenge

Question

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.

1. Size of machine - easy: a 5-state machine beats a 7-state machine
2. 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?

EDIT

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.

Answer 1

I think you should score machines on the number of rows in its transition table.

A simple, uncompressed table has (State * Colors) rows and 5 columns, organized like below. I can't really find any solid reference for the correct order of columns, but that doesn't matter.

cur state   cur color   new state   new color  direction
0           0           1           2          left
0           1           0           0          right
2           2           -           -          halt
...

This would imply that scores should be states*colors, but I think there's more to it. For example, there is potential for a lot of redundancy in these rows, like if there are a lot of cur-state/cur-color combinations that produce the same new-state/new-color/direction combination.

My suggestion is to create/standardize a more "compressed" notation for these tables and then score Turing machines on the number of rows in the compressed tables. A table that is more compressible should indicate that a given machine is simpler than a machine with the same number of states/colors. This allows for finely-grained scoring.

Below are some ideas for transition table compression that can stacked on to each other.

Idea 1: Using _ for unspecified

In many cases, it is possible to leave details out of the table to cover more cases in fewer lines. I will denote unspecified information with _. If there is a _ in the cur-state/cur-color columns, then that indicates that all states/colors can go there. If there is a _ in the new-state/new-color column, then that indicates that the state/color remains the same.

cur state   cur color   new state   new color  direction
2           _           1           _          left
for a 3 state, 3 color machine, equals
2           0           1           0          left
2           1           1           1          left
2           2           1           2          left

Idea 2: Allow "conflicting" rules to appear on the table

The table is usually interpreted as a series of If-Then statements with no fixed order. This would basically change it to a series of Else-If-Then with a fixed order.

cur state   cur color   new state   new color  direction
2           0           1           2          left
2           _           1           _          left
for a 3 state, 3 color machine, equals
2           0           1           2          left
2           1           1           1          left
2           2           1           2          left

Idea 3: Auto-halting

Instead of requiring a row for each halting condition, we can simply say "If no rule on the table applied, then it halts." This can probably save a line or two in most tables.

Answer 2

Googology wiki founder and administrator Nathan Ho, known on said wiki as Vel! (formerly FB100Z), has proposed the following metric for scoring TMs:

score=states * colors^2

Adding 1 to the number of states if any null tape movements are used.

I personally think the exponent of 2 is a little high and would prefer something like 3/2 instead, and see no need to include a penalty for null tape movements; but that's the scoring metric he used.

I think something along these lines would be reasonable for a TM-only challenge, but when they're used along side other languages, I would suggest submitting a rule table in some reasonable format (such as the one used here) and scoring by the size of the rule table.

Answer 3

For scoring runtimes, I think you'll have a better time judging total number of steps on some test cases you provide than by asymptotic complexity. A numerical runtime score is easier to combine with a number of states to produce an overall score by some formula, though you need care in making the formula to make their be legitimate tradeoffs. Also, this incentivizes algorithms to improve constants as well big-O's.