# Language and Decidability Problems for Turing Machines

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

– D.W.
Commented Nov 23, 2021 at 6:07

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