3

Are there general methods / algorithms for finding a Turing Machine that will output a given binary number?

For example, I want the machine to write 0111001101111001110110001110110011000010110100101101110 on a blank tape and then halt. Is there a general way to find a machine that does that?

I could try random machines, or enumerate all 10-state machines, or something, but that would be ridiculously slow, so I'm wondering whether/where the idea has been explored. I'm asking here because I frankly don't even know what keywords to search for on the googles.

Background : I just think it would be a cool form of extreme compression, with no practical purpose but recreation.

SCH
  • 145
  • 7
  • You could implement a machine that runs an algorithm that writes a given number. It's absolutely doable. – Ali Caglayan Jun 01 '16 at 16:05
  • It is not clear what you are asking. Clearly a Turing machine can write any given finite list of symbols. Are you asking for the 'smallest' machine that will write the string? – copper.hat Jun 01 '16 at 17:31
  • @copper.hat the OP is asking whether there exists an algorithm that can take as input a description of a Turing Machine and then determine if that M will produce a given output. By Rice's Theorem the answer should be no. – user137481 Jun 01 '16 at 17:50
  • I think it is asking if there exists $M$ that will produce the given number, and such an $M$ clearly exists. That is my read of the first sentence. – copper.hat Jun 01 '16 at 17:53
  • Thanks for the replies, and I'm sorry I wasn't clear. @copper.hat is right : I know such a machine exists, what I would like is a method to algorithmically *find* the smallest one possible, or at least one smaller than a machine containing the string. the initial idea was compression of the string. – SCH Jun 01 '16 at 18:14
  • 2
    Such an algorithm would allow you to compute the [Kolmogorov complexity](https://en.wikipedia.org/wiki/Kolmogorov_complexity) of arbitrary strings, which is [undecidable](https://en.wikipedia.org/wiki/Kolmogorov_complexity#Uncomputability_of_Kolmogorov_complexity). – cardboard_box Jun 01 '16 at 22:26
  • I don't think so : it would only search among the TMs smaller than the original string, of which there is a finite amount. It could just enumerate all the TMs with less than $m$ states and keep the smallest one that outputs the string. So it's possible, though cosmically computationally expensive. I guess I'm not asking for a general algorithm which finds the optimal TM for any string, but rather a working algorithm with some chance to find an answer before the heat death of the universe. – SCH Jun 02 '16 at 11:24

1 Answers1

3

It is doable with some additional constraints.

If you fix the parameters of the machine (alphabet, tape alphabet, number of states, starting/accepting state) and put a bound of the maximum amount of memory and computation steps to be used, the problem of finding the transition function (which essentially captures the logic of the Turing machine) can be formulated as a SAT instance - you can look at the proof of Cook's theorem for inspiration how to specify that or look into FOL model finding techniques. Then you continue depending on what you definition of "minimal" model is. Assume it is simply the number of states. Then you leave all the other parameters fixed and solve the SAT problem with decreasing value in the parameter. The last instance that returns "satisfiable" as an answer is your minimal model.

I have done a similar thing using Answer Set Programming myself and it was ~80 LOC. Note that this only works in theory (or for very small inputs, where actual compression can hardly be even achieved) and is intractable in practice.

If lossy compression would be acceptable, you could minimize the Hamming distance of the desired string from the actual output of the model and get some solution earlier (a little bigger instance would become tractable), perhaps you could even use genetic algorithms or other heuristic optimization techniques to do this, but we are getting really scruffy here. Alternatively, you could choose a finite model like Mealy automaton to minimize, assuming some known input.

SCH
  • 145
  • 7
user1747134
  • 112
  • 12
  • Well, *thank you* for the infodump / pointers, I now have homework to do, but the _fun_ kind where I read wikipedia articles and the arxiv. I'd kinda lost hope on this question, so it's extra nice. – SCH Jul 10 '18 at 19:37