Is a Turing Machine that only takes strings of the form $0^*$ Turing Complete?

Question

You have a Turing machine that only processes input on the form $0^*$. If it is given an input without 0's, it will simply halt without accepting or do anything else. Is it Turing Complete?

The set $0^*$ is countably infinite, since you can make the bijective function $f(x) : 0^* → \mathbb{N} $:

$f(x) = length(x)$

Where $length(x)$ is the length of the string (so you treat them as Peano Numbers).

I understand that the set of all programs (the programs that a Turing machine can run) are countable, and that the set of a Turing machines are also countable. But, can the set of string that the Turing machine can process (with no guarantees of halting) only be countably infinite (as in this case), or does it have to be uncountable?

My understanding of undecidable problems with regards to Turing machines is that they arise because there are languages that have a cardinality strictly greater than the natural numbers, e.g. $B^*$, where $B = \{0,1\}$, which has a cardinality equal to the real numbers. It seems to me that, although you can encode any integer with the language $0^*$, you can't encode an arbitrary language. The problem is: how can you encode recursively enumerable languages when all you have is unary notation? If this is indeed impossible (though I have a feeling it is possible; I can't see how the representation of numbers should be a fundamental hindrance), then it turns out that this particular Turing machine is not Turing Complete (or maybe you would say that it is not really a Turing machine).

Answer 1

It looks like Turing machines remain Turing-complete when the alphabet is restricted to have one symbol, $0$. First, preprocess your input by replacing every $0$ with $0\square$, where $\square$ is the blank symbol. Now, you can simulate a 2-symbol alphabet by using $0\square$ to represent zero and $\square0$ to represent one.

My understanding of undecidable problems with regards to Turing machines is that they arise because there are languages that have a cardinality strictly greater than the natural numbers

This is incorrect. A language is, by definition, a set of finite strings and there are only countably many finite strings over any finite alphabet (proof: you get a bijection with the natural numbers by treating each string as a number written in base-$k$, where $k$ is the size of the alphabet). However, there are uncountably many different languages and that observation along with the countability of the set of Turing machines lets you deduce that there must be some undecidable langauges.

It seems to me that, although you can encode any integer with the language 0∗, you can't encode an arbitrary language.

This is also incorrect. You can encode any natural number $n$ with the single string $0^n$ and, therefore, you can code any set of natural numbers with a unary language, i.e., a subset of $0^*$. And you can code any set of natural numbers as a language. You can also code any language over an alphabet of size $k>1$ by using the base-$k$ trick I described above.