patternMinor
Matching Lemma with infinitely many symbols
Viewed 0 times
infinitelywithlemmamanymatchingsymbols
Problem
I was reading about Universal Turing Machines.
I see that the matching lemma states, that between two symbols X and Y, if there are only 1-s and blanks, then a TM exists, which can count the number of ones.
This is used to match strings of ones between two tapes.
Now I wonder, would there also be a TM or a method of implementation of a TM which can match two strings? To me it intuitively appears, that inifinitely many symbols implies infinitely many states for the machine, and an example workflow may look like:
found symbol X, enter state stateX, exit stateX to state readnextchar if again X was found on the second tape.
Would that not mean an infinitely long transition table? or is there an way to represent a table in a smaller way?
if the symbols are represented via some kind of place value system, e.g. decimal, binary, would that shorten the transition table length?
I see that the matching lemma states, that between two symbols X and Y, if there are only 1-s and blanks, then a TM exists, which can count the number of ones.
This is used to match strings of ones between two tapes.
Now I wonder, would there also be a TM or a method of implementation of a TM which can match two strings? To me it intuitively appears, that inifinitely many symbols implies infinitely many states for the machine, and an example workflow may look like:
found symbol X, enter state stateX, exit stateX to state readnextchar if again X was found on the second tape.
Would that not mean an infinitely long transition table? or is there an way to represent a table in a smaller way?
if the symbols are represented via some kind of place value system, e.g. decimal, binary, would that shorten the transition table length?
Solution
Turing machines can simulate whatever algorithm you can actually program. So if you can solve your problem by writing a program in C or python (for example), then a Turing machine can also solve your problem.
The most general statement of this principle - everything that is computable can be computed using a Turing machine - is known as the Church-Turing hypothesis. For the specific case of languages like C or python, we know that this hypothesis is true - in principle you can convert every program in C or python to an equivalent Turing machine. The Turing machine would be a lot slower, though. (But only by a polynomial amount!)
For your specific problem, you can allocate a specific location in the tape for your the variables you need, and then update them as you go. The number of states in the Turing machine is proportional (more or less) to the number of instructions in assembly code for your algorithm. Actually programming Turing machines is hard and somewhat pointless. Memory handling is particularly awkward, but Turing machines can implement arrays, tables, and other data structures by allocating special areas on the tape and maintaining them. Perhaps you will hear more about that later in your class.
Finally, for the reason you mention, the tape alphabet is always finite. Without loss of generality, we can assume that it contains only zero and one, though that might make programming the Turing machine even harder. Data structures such as strings and numbers can be encoded in just the same way that they are encoded in your computer - as a string of zeroes and ones.
The most general statement of this principle - everything that is computable can be computed using a Turing machine - is known as the Church-Turing hypothesis. For the specific case of languages like C or python, we know that this hypothesis is true - in principle you can convert every program in C or python to an equivalent Turing machine. The Turing machine would be a lot slower, though. (But only by a polynomial amount!)
For your specific problem, you can allocate a specific location in the tape for your the variables you need, and then update them as you go. The number of states in the Turing machine is proportional (more or less) to the number of instructions in assembly code for your algorithm. Actually programming Turing machines is hard and somewhat pointless. Memory handling is particularly awkward, but Turing machines can implement arrays, tables, and other data structures by allocating special areas on the tape and maintaining them. Perhaps you will hear more about that later in your class.
Finally, for the reason you mention, the tape alphabet is always finite. Without loss of generality, we can assume that it contains only zero and one, though that might make programming the Turing machine even harder. Data structures such as strings and numbers can be encoded in just the same way that they are encoded in your computer - as a string of zeroes and ones.
Context
StackExchange Computer Science Q#10627, answer score: 4
Revisions (0)
No revisions yet.