Unary Halting Problem

Question

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.

Answer 1

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

Answer 2

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.