Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I have some difficulties in understanging what's actually a unary halting problem

Few examples of unary languages are following:

$A=\{1^k\space |\space k\space is\space even\}$

$B=\{2^k\space |\space k\space is\space prime\}$

In other words unary language is a language of strings consisted of one symbol and encode the length.

Halting problem is just a description of Turing Machine and it's input, decide whether the given Turing Machine halts on the given input.

The following is the description of unary halting problem:

The unary halting problem is a special case of the halting problem, where a unary encoding is used for both the program and the input.

So far I haven't found any more formal definition of unary halting problem. For me it's not obvious how to encode halting problem into unary language.

I would appreciate for a formal definition or any explanation what's unary halting problem.

share|cite|improve this question

You probably understand how to encode the halting problem $H$ with some alphabet. Now assign every character in your alphabet to a unique string over $\{0,1\}$, such that every character gets a code with the same length. By replacing every character with its code you get an encoding over the binary alphabet. To map your binary encoding to an integer, just add a leading 1 and interpret this $0,1$ string as binary number, say $k$. Then the instance in the unary encoding is simply $1^k$.

share|cite|improve this answer

The halting problem is:

Is there a turing machine $H$ which, given a description of a turing machine $M$ and an input $i$, answers the question: does $M$ halt when given input $i$?

The description of $M$ and the input $i$ must be written somehow in symbols. You can always interpret these symbols as numerals. If there are $N$ possible symbols, you can interpret a sequence of symbols as a base-$N$ numeral. So you can rephrase the halting problem as:

Is there a turing machine $H$ which, given a number that represents a turing machine $M$ and a number that represents an input $i$, answers the question: does $M$ halt when given input $i$?

But numbers can be represented in many ways, so we could take the number that represents some turing machine, and instead of writing it as a sequence of characters, or as a sequence of decimal digits, or as a sequence of bits, we could write it in unary format.

Is there a turing machine $H$ which, given a unary numeral that represents a turing machine $M$ and a unary numeral that represents an input $i$, answers the question: does $M$ halt when given input $i$?

A turing machine can easily convert numbers between any of these formats, so the problem is the same.

share|cite|improve this answer
Is it worthwhile to mention that this relies on the fact that Turing machines are countably infinite? Implicit in representing a Turing machine as unary numeral is a function that maps natural numbers at least surjectively to Turing machines. – Tim Seguine Jan 17 '13 at 18:01

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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