3
$\begingroup$

For a string $w$, $M_w$ denotes the Turing machine whose encoding is $w$.

I want to reduce the language $L=\{w \mid |T(M_w)| \geq 42\}$ to $H_0 = \{w \mid M_w \text{ halts on } \epsilon\}$, but I can't find a way to define an algorithm that halts only if $w \in L$. Either way:

  • if $w \in L$ I would have to find at least 42 words that are in $T(M_w)$, which might be undecidable for certain languages.
  • if $w \notin L$ then $M_w$ would accept only 41 or less words. Then we do know, that the language $T(M_w)$ is regular, but still we can't test if the language is regular or not.

Simply trying random words until we have at least 42 doesn't work as for some words the TM will not halt.

Is there any idea I could try? Or in other words: how would one prove $L \leq H_0 $?

$\endgroup$
  • $\begingroup$ I'm not sure how regularity enters the picture. $\endgroup$ – Yuval Filmus Jun 1 at 15:12
  • $\begingroup$ This was just an idea to try to find out if w is not in L. Because all languages with a fix amount of accepted words is regular. So I thought maybe we can decide if its regular or not.. $\endgroup$ – gxor Jun 1 at 15:14
2
$\begingroup$

This answer assumes that $T(w)$ is the set of inputs that the Turing machine $M_w$ halts on.

Given a Turing machine $M$, construct a new Turing machine which runs $M$ in parallel on all inputs. Once $M$ has halted on 42 different inputs, halt. (If this never happens, the new machine will never halt.)

In order to run $M$ on infinitely many inputs, you do the following:

  • Start with some enumeration $x_1,x_2,\ldots$ of all inputs.
  • Run $M$ for one step on $x_1$.
  • Run $M$ for one step on $x_1,x_2$.
  • Run $M$ for one step on $x_1,x_2,x_3$.
  • And so on.

This is known as dovetailing.

The argument above reduces $L$ to the halting problem, and so shows that $L$ is r.e. We can also reduce the halting problem to $L$, hence showing that $L$ is r.e.-complete. To do this, suppose that we are given a Turing machine $M$ as input to $H_0$. We construct a new Turing machine which:

  • On input $\epsilon$, transfers control to $M$.
  • On input $0,00,\ldots,0^{41}$, halts.
  • On all other inputs, doesn't halt.

The new machine belongs to $L$ iff the original one belongs to $H_0$.

$\endgroup$
  • $\begingroup$ Can we build a turing machine that simulates a turing machine on all possible inputs in parallel? This would mean the turing machine would need to have infinite bands?! $\endgroup$ – gxor Jun 1 at 15:17
  • $\begingroup$ Yes, this is a standard construction, known as dovetailing. You must have seen it in class. $\endgroup$ – Yuval Filmus Jun 1 at 15:36
  • $\begingroup$ Yes I've seen that. But if we'd have infnite machines and run through all the machines to execute n steps on that machine, wouldn't this "first" Step take forever? Im sorry to ask that many questions! $\endgroup$ – gxor Jun 1 at 15:39
  • $\begingroup$ That's not how dovetailing works. You execute a step on the first machine, then you execute a step on the first two machines, then on the first three machines, and so on. $\endgroup$ – Yuval Filmus Jun 1 at 15:47
  • $\begingroup$ Thank you!!I think I understood! We could like this: 1. construct all inputs with length 1, run 100 steps on that. 2. on track 2 construct the machine with inputs of length 2, run machines on track 1 (input length 1) for 100 steps then run track 2. Continue like this! $\endgroup$ – gxor Jun 1 at 15:49

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.