1
$\begingroup$

Yet another question from an exe. in the Computability class taught by Z. Luria -

I'm not really sure how to prove the undecidability, moreover, didn't a finite language always decidable?

I mean we can build a machine $M$ that checks all the possibilities (In this case ${0, 1, 00, 01, 10, 11}$), That was my approach for proving the recognizable property.

Is there a mistake in the exe. or I'm not understanding the topic at all?

I think that the fact the language is made of $TM$ confuses me.

$\endgroup$

1 Answer 1

1
$\begingroup$

Undecidability can be confusing. Recognizability can be confusing.

The setups and arguments for propositions on undecidability or recognizability can be quite confusing, indeed. The languages we want to prove undecidable/recognizable usually involve encodings of Turing machines, while at the same time, the programs that we build to prove them undecidable/recognizable are also Turing machines.

For example, the halting problem is to decide, given the encoding of a Turing machine and a word, whether that Turing machine will halt upon that word (as input). The usual proof that the halting problem is undecidable involves:

  • a hypothetical Turing machine $A$ that decides the halting problem,
  • the construction of a new Turing machine $B$ that will, given an encoding of a Turing machine $p$ as input, run forever iff $p$ halts upon the encoding of $p$ itself, and
  • the analysis of running $B$ upon its own encoding as input.

It happens often when people talk about a Turing machine, they mean the string that encodes it instead. For example, the language of all Turing machines that accept empty input. In case of confusion, make it clear what is referred to is the machine, or the string instead.

Let us clear some confusions

While "a finite language always decidable", this problem is about the decidability of the language of the encodings of some Turing machines. That is, whether there is an algorithm that will always tell (in finitely many steps), given an encoding of a Turing machine $T$, whether $T$ accepts every string among $\epsilon,0,1,00,01,10,11$. There are, of course, infinitely many Turing machines that accepts all those strings. For example, Turing machine $T_i$ that always moves to the right $i$ times and then accepts, ignoring input completely. You can also add an arbitrary number of useless states to a Turing machine.

"The language is made of TMs confuses me". Language $H2$ is made of the encodings of Turing machines. $\langle .\rangle$ maps a Turing machine to the string that encodes it, i.e., given Turing machine $M$, $\langle M\rangle$ is a string.

Prove $H2$ is recognizable but not decidable.

$H2$ is not decidable is a straightforward application of Rice's theorem. All we need to do is to verify that it is valid to apply Rice's theorem.

Let Turing machine $R$ runs as follows upon input string $w$.

  1. If $w$ does not encode a Turing machine, reject.
  2. Otherwise, $w$ encodes a Turing machine $T$.
    1. Simulate $T$ upon the empty input.
    2. If the simulated $T$ above accepts, simulate $T$ again upon input string 0.
    3. If the simulated $T$ above accepts, simulate $T$ again upon input string 1.
    4. If the simulated $T$ above accepts, simulate $T$ again upon input string 00.
    5. If the simulated $T$ above accepts, simulate $T$ again upon input string 01.
    6. If the simulated $T$ above accepts, simulate $T$ again upon input string 10.
    7. If the simulated $T$ above accepts, simulate $T$ again upon input string 11.
    8. If the simulated $T$ above accepts, accepts.

It is clear that $R$ recognizes $H2$.

$\endgroup$
1
  • $\begingroup$ Thank you for such a detailed and helpful response! $\endgroup$
    – RedYoel
    Apr 5 at 15:09

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.