Infinite alphabet Turing Machine

Question

Is a Turing Machine that is allowed to read and write symbols from an infinite alphabet more powerful than a regular TM (that is the only difference, the machine still has a finite number of states)?

Intuition tells me not, since you need an infinite number of states to differentiate each symbol. So I think some of the symbols or the transitions caused by the symbols (or some subsets of the transitions) have to be equivalent. So you can actually simulate such machine with a regular TM and a bounded subset of such symbols or transitions.

How could I approach a formal proof of this?

Answer 1

No, it would be more powerful. The transition function would no longer be finite, and that buys you a lot of power.

With an infinite alphabet, you can encode any input item from an infinite set in one symbol (although the input set can't be "more infinite" than the alphabet set, e.g. the alphabet would presumably be only countably infinite, so elements of uncountable sets like the real numbers couldn't be represented in one symbol). And likewise for the output.

So you can make a two-state (one initial, one accept) infinite-alphabet-TM with a single transition that moves to the accept state and changes the symbol under the tape head in accordance with the function you're trying to compute. This recipe would allow you to compute any mapping between sets that can be put in a one-to-one correspondence with the alphabet.

So to avoid that degenerate sort of machine being the answer to everything, you'd need to restrict what the transition function can do. An obvious one would be to require the transition function itself to be computable (ordinary TM's transition functions are trivially computable after all, since they're finite). But then you'd be trying to use computable functions to define your model of computable functions.

Answer 2

The above answer is correct, but there is a little more that can be said about infinite alphabets and computability.

A Turing Machine is described in WP as $M = (Q, \Gamma,b,\Sigma,\delta, q_0, q_f)$ in which all sets are finite. Thus the transition function $$ \delta: Q / F \times \Gamma \rightarrow Q \times\Gamma \times \{L,R \} $$ is necessarily finite.

In an infinite alphabet machine we would replace the input alphabet $\Sigma$ by say $\Sigma^{inf}$ and so the tape alphabet by $\Gamma^{inf}$ and the transition function by $\delta^{inf}$ obeying:

$$ \delta^{inf}: Q / F \times \Gamma^{inf} \rightarrow Q \times\Gamma^{inf} \times \{L,R \} $$

So $\delta^{inf}$ is necessarily an infinite function. As remarked if this function is to be non-computable, then the above is not representable finitely. Let us assume that we shall keep $\delta^{inf}$ (partial) recursive if possible. The question is whether the alphabet will always allow this.

The basic issue is that a finite alphabet is presented in its entirety (so we can choose to define our functions recursively), but an infinite alphabet can never be presented in its entirety. So what mechanism is generating the alphabet?

The simplest way to consider this is to imagine that there is a finite "core" alphabet, say $A=\{a,b\}$. Then generate a language $L \subset A^*$. Assume that string abaab $\in L$. Then define $\alpha = <abaab> \in \Gamma^{inf}$. So the infinite alphabet consists of sets of strings from $L$ concatenated into a single symbol like $<abaab>$.

The simplest such alphabet is basically <1*>, the regular language in which any two symbols are distinguished by counting the number of vertical strokes in each symbol. This will be computable with a finite state parser (as an LBA though, not as a Finite Automata). Turing argued for a finite alphabet to avoid any appearance of a non-finite operation in a TM operation. However it is worth noting that the 26 letters of the English alphabet do not follow this counting pattern: letter z does not contain 26 strokes or dots or anything. So other patterns are possible with the most general computational pattern that based on a recursively enumerable (r.e.) language $L$.

The problem here though is that constructing $\delta^{inf}$ will not be possible unless the definition of $L$ is explicitly provided. This is partly because equivalence of r.e. sets is undecidable and partly because otherwise we only ever have a finite sample to work with and cannot infer $L$ from that. If we do have the definition of $L$ (and hence $\Gamma^{inf}$) then if $f$ is recursive in $\Gamma^{inf}$ then $f$ is recursive in finite A, and so $f$ is absolutely recursive and $\delta^{inf}$ can be recursive.

Finally we consider the case that $L$ is not r.e. with two examples:

Example1. $<n>\in \Gamma^{inf}$ iff $\phi_{n}(n)$ provably diverges. In this case the alphabet $\Gamma^{inf}$ will obviously not have a finite description - instead it will "grow" over time (and only be fully defined itself in some computational limit). But then it is an infinite alphabet which cannot be presented at once in any case. So if $f$ is recursive in $\Gamma^{inf}$, then f is in $\Delta_2^0$ - the Halting set. So $\delta^{inf}$ cannot be recursive.

Example2. A more geometric example considers Penrose-like Tiles. Let symbol $S\in\Gamma^{inf}$ if $S$ is a unit of N aperiodic tiles which provably can tile the plane. This alphabet is infinite since one can construct, for any N, an N-tile unit of Penrose tiles. However tiling the plane itself is undecidable, so the set of S will grow as more tiles like this are discovered. A possible $f$ recursive in $\Gamma^{inf}$ but not absolutely recursive might be f(S) = number of tiles in S.