One way to talk about a "problem" or computation is as a set of pairs- the inputs paired with the outputs. For example, the problem of adding one to a natural number is the set {(n, n+1) | n a natural number}. For more complex problems the input is some encoding of the problem, like a list of cities for the Traveling Salesmen Problem, or a list of number that we want the average of. No matter what problem we chose, it is possible to encode the inputs as strings of bits ({0, 1}*). The output will be similarly encoded, and can be in whatever form we want. If the problem is a decision problem (given a number encoded in decimal, is this number prime?) they the answer may be interpreted by running the machine and looking at the first symbol on the tape (assuming we are using a tape infinite to the right but not to the left) as if it is a 1 then the number is prime and if it is a 0 then the number is composite. We could also spell out "the number is prime" or any other way we want. Notice, by the way, that the pairs of inputs and outputs are very much like functions, although they may be partial in the sense that for some input there may not be a solution (or the computation may not halting on that input).
Notice that a machine may be given a string of symbols that don't encode a solution to the problem we expect it to solve. This is a perfectly well defined situation- if it halts then the machine in some sense defines a larger problem then we defined for it (it comes up with some solution to some problem, although probably not a very interesting one). We don't concern ourselves with the action of a machine on arbitrary inputs for the most part- we just ignore the extra possible solutions.
Similarly, a Turing Machine can be encoded by writing down each part of its data, as we saw in a recent post. It doesn't matter how we do it- its only important that there be at least one way. This means that we can encode a machine and its input and concatenate them, resulting in a single computation. This suggests that we could pass this encoded machine + input into another machine. This brings us to the idea of a Universal Turing Machine- a Turing Machine is called universal if every other machine and input to that machine can be encoded such that the result of the universal machine U on encoded machine M and input I is the same as running M on I. In other words U(M, I) = M(I). These machine are interesting because they solve every possible problem if given an instance of the problem and a solver. Universal machine play an important role in automata theory, although I know nearly nothing about this part of Computer Science.
One other thing I wanted to mention about Turing Machines is the blank tape machines. A blank tape machine is a machine that expects to start out with a tape with all blanks. It turns out that given some machine M and input I, we can construct a machine M' such that if we run M' on a blank tape we get the result of running M on I- M'(_) = M(I). This can be interpreted by saying that a program can take input or we can hard-code the input in the source code.
No comments:
Post a Comment