0
$\begingroup$

Below are the two problems Im working on and my attempt at a solution (understanding the question). My first question is am I interpreting the question from the symbols right, second can you help explain what I need to do for these questions? Ive been reading through chapter 4 of Sipser 3rd ed. Intro to theory of computation and I haven't been able to make much sense the questions. Any help is appreciated.

  1. Show that the following languages are partially decidable:

    (a) ETx = {<M, x> | M(x) ↓ and at the end of computation the tape of M is empty}

    ETx is a universal TM M with input x that terminates and at the end of computation the tape of M is empty. Not sure where to go from (restating the question...)

    (b) ETE = {< M > | (∃x)(M(x) ↓ and at the end of computation the tape of M is empty)}

    ETE is a universal TM M where there exists some input such that input X terminates M and at the end of the computation the tape of M is empty...


  1. Show that the language ETx is not decidable. (Hint: Describe how a decision procedure for ETx could be used to decide the universal language Lu.)

    Not sure where to begin with this one


$\endgroup$
1
  • 1
    $\begingroup$ Please ask only one question per post. $\endgroup$
    – D.W.
    Commented Nov 23, 2021 at 6:07

1 Answer 1

0
$\begingroup$

Let's start with the first question. One can recursively enumerate triples $\langle M, x, t \rangle$ and print $\langle M,x\rangle $ or $M$ (depending on whether we consider the first or the second language) in case $M$ halts on input $x$ within $t$ steps and the tape is empty when $M$ halts.

For the second question we can reduce halting problem to the language a) by mapping a Turing machine $M$ to a pair $\langle M', M\rangle$, where $M'$ is defined as the Turing machine which runs the Turing machine $M$ (whose encoding it receves as its input) and which clears the computation tape if $M$ halts. Clearly $M$ halts on empty input iff $\langle M', M\rangle$ belongs to the language a).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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