# Matching Lemma with infinitely many symbols

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?

You can allow inifite alphabets because they can be modeled to fit the original Turing machine model.

Assume without loss of generality¹ that the alphabet is $\mathbb{N}$. Then, any tape content

$\qquad n_1 n_2 \dots n_k$

can be translated to a $\{0,1\}$-encoded TM tape like this:

$\qquad \# \operatorname{bin}(n_1) \# \operatorname{bin}(n_2) \# \dots \# \operatorname{bin}(n_k) \#$,

where $\operatorname{bin}(a)$ is the binary encoding of $a$.

Of course you also have to translate the transition function. So, if you have $(a,q) \to (b,q')$ in the original machine, you'll need a chain of otherwise irrelevant states that accepts $\operatorname{bin}(a)$ while moving from $q$ to $q'$.

Now, this assumes you'll still have a finite state graph and transition function. Note that this is not a restriction: you can easily implement counters on the tape (as opposed to in the states).

1. There are models on uncountable alphabets; these are not compatible in general.
• thank you, this actually answers my question, thank you very much. – Sean Mar 20 '13 at 18:46

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.