0
$\begingroup$

This imprecise question is about a simple example for the following problem.

I would like a Turing machine with few states that accepts only inputs which look complicated to the naked eye.

Of course the Kolmogorov complexity of the lexicographically smallest such input would be at most a constant more than the size of the Turing machine, so this makes the question impossible to define presicely, but hopefully it is clear what I mean. For example, a TM that accepts only Carmichael numbers would do, but I'm looking for a TM with very few states.

$\endgroup$
4
  • $\begingroup$ What do you mean by "very few states"? 5? 10? 50? 100? 1000? $\endgroup$
    – nir shahar
    Dec 18, 2021 at 13:53
  • $\begingroup$ As few as possible. $\endgroup$
    – domotorp
    Dec 18, 2021 at 14:53
  • $\begingroup$ This sounds pretty subjective -- in particular "complicated to the naked eye" sounds pretty murky and subjective. You appear to be asking for a precise answer to something that seems likely to be fairly subjective. It is easy to come up with simple-to-state algorithms with that property; e.g., define a hash function $h$ and only accept inputs $x$ such that $h(x)=0$. Converting that to a Turing machine sounds tedious and unenlightening. $\endgroup$
    – D.W.
    Dec 19, 2021 at 8:38
  • $\begingroup$ @D.W. Hash functions after conversion are likely to have many states. Imagine it like the challenge to compute the values of the busy beaver function or like a code jam. I can understand that not everyone is into finding such examples but I think of it as a nice puzzle problem. $\endgroup$
    – domotorp
    Dec 19, 2021 at 10:10

1 Answer 1

1
$\begingroup$

Here is an algorithm that can be implemented with a Turing machine using a small number of states, and that only accepts inputs that I suspect are likely to look complicated to most humans. Let the bits on the tape be $T[1,\dots,n]$:

  • For $i:= 1,2,\dots,8$:
    1. For $j:= 3,4,\dots,n$:
      • Set $T[j] := T[j] \oplus (T[j-1] \land T[j-2]) \oplus C[i]$.
    2. For $j:= n-2,n-3,\dots,1$:
      • Set $T[j] := T[j] \oplus (T[j+1] \land T[j+2]) \oplus C[i+8]$.
  • If $T[1]=0$, accept, otherwise reject.

Above $\oplus$ represents xor, $\land$ represents logical-and, and $C[1..16]$ represents a constant that is filled with random bits at design time.

Notice that this algorithm can be implemented in a Turing machine with about 64 states.

(How does this work? It is implementing an unbalanced Feistel network. So, you can think of it as roughly approximating the following conceptual approach: fix a random permutation $\pi$ on $n$-bit strings, then apply $\pi$ to the input and accept if the first bit of the result is 0.)

Probably "8" above is overkill, so I'm guessing you can significantly reduce the number of states needed. It will be subjective how small you can make it and still have the accepted inputs look random to the human eye, but I'd bet that "2" is enough, which would leave you with a Turing machine that uses only 16 states.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.