4
$\begingroup$

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).

$\endgroup$
  • 2
    $\begingroup$ The question you're trying to formulate is: can there be a universal Turing machine over am alphabet with a single letter? $\endgroup$ – Gilles Apr 26 '14 at 11:58
  • $\begingroup$ @Gilles that's right. $\endgroup$ – Guildenstern Apr 26 '14 at 12:31
6
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ With regards to your simulation of the 2-symbol alphabet using blanks, is that something that you think is strictly necessary in order to express any possible input to the Turing machine? Or is this more of a simple demonstration to show that the familiar 2-symbol alphabet can still be used, but it isn't really necessary, and that you could get by with only using unary notation? Phrased differently: would it still be Turing Complete (or Universal) if you weren't able to use the blank symbol to encode the 2-symbol alphabet? $\endgroup$ – Guildenstern Apr 26 '14 at 16:45
  • 1
    $\begingroup$ I'm not sure if the two-symbol trick is necessary or not. It just seemed to be the simplest way to sketch out a proof. $\endgroup$ – David Richerby Apr 26 '14 at 16:47
  • $\begingroup$ ^ Yeah, it feels like the most intuitive encoding. If one isn't allowed to use blank symbols as part of any encoding, then the only way I see how this could work is if every input is treated like a single integer, since I don't see a way of delimiting the different parts of the input (e.g. you can't express three integers as input, since you don't know where each of them begin). In that case, the set of inputs is countable, which seems to imply that the machine is not Turing complete. $\endgroup$ – Guildenstern Apr 26 '14 at 16:58
  • 1
    $\begingroup$ The input of any Turing machine is a finite string drawn from a finite alphabet. There are only countably many of those. Also, it's easy to encode multiple natural numbers into a single one: for example, you can code $\langle x,y,z\rangle$ as $2^{x+1}3^{y+1}5^{z+1}$ ("$+1$" so that zeroes aren't a problem). $\endgroup$ – David Richerby Apr 26 '14 at 17:53
  • $\begingroup$ Hmm, then I don't see any way that this Turing machine is not Turing complete any more. $\endgroup$ – Guildenstern Apr 27 '14 at 15:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.