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