Diagonalization for Etm

174 Views Asked by At

$E_{TM} = \{\langle M\rangle\mid M$ is a TM and $L(M) = \emptyset\}$

We want a proof by diagonalization to show that $E_{TM}$ is undecidable. But the form of inputs are like $<M>$ and the Table of Computation has only one row. In $A_{TM}$ how ever the form of inputs were $<M,w>$ which makes a 2-dimensional matrix of computation that we can make a $TM$ which is $DIAG$ such that do the opposite of $A_{TM}$ for a inputs like $< M_i,<M_i>> $ but in $E_{TM}$ i have a trouble to make such machine which leads me to a contradiction.

I have tried to make a $TM$ which is made from $E_{TM}$ and takes 2 inputs and run equivalent $TM$ for $E_{TM}$ for both of them and accept if and only if both of them accept or in another version non-of them accept but no contradiction happened in these 2 cases.

Please help me to do diagonalization for $E_{TM}$ , Thanks

===EDIT===

I Try another method and i guess it is right :

We make a $TM :H^\prime$ with $TM: H$ which is a decider for $ETM$

$H^\prime(<M_1>,<M_2>) := H(<M_1>)\ \land H(<M_2>)$

and we know logical and is decidable so, we now define $TM: D$

$D(<M>) := \\ \textrm{if}\space H(<M>)=1 \space \text{accept} \space \text{all} \\ \textrm{if}\space H(<M>)=0 \space \text{reject} \space \text{all}$

I think this leads us to a contradiction if im not wrong because:

$H^\prime(<D>,<D>) = H(<D>)\ \land H(<D>) = d \\ \text{if}\space d=1 \space \text{Then}\space H(<D>)=1 \space\text{Then}\space L(D)=\emptyset \space\text{Then}\space D \space \text{accept}\space\text{all} \space\text{Then}\space L(D)\neq \emptyset \Rightarrow \bot \\ \text{if}\space d=0 \space \text{Then}\space H(<D>)=0 \space\text{Then}\space L(D)\neq \emptyset \space\text{Then}\space D \space \text{reject}\space\text{all} \space\text{Then}\space L(D)= \emptyset \Rightarrow \bot$

please correct me if i made a mistake. Thanks

1

There are 1 best solutions below

0
On

If you are trying to define TM D as $D(<M>)=\begin{cases} \text{accept all}, & H(<M>)=1 \\ \text{reject all}, & H(<M>)=0 \end{cases} \: $ then the question is about 'all'. You can accept or reject only input word $ <M> $ so 'accept all' means $D(<M>) = 1$ and 'reject all' means $D(<M>) = 0 \,$ for a specific TM $M$. It's better to define TM D as $D(x)=\begin{cases} 1, & H(<H>)=0 \\ 0, & H(<H>)=1 \end{cases} \: $, so $D(x)= \begin{cases} 1, & L(H) \ne \varnothing \\ 0, & L(H) = \varnothing \end{cases} \:$. Depending on $ L(H) $ language $ L(D) $ is empty or contains all possible input strings.

Now try to define the value $ H(<D>) $. If $ H(<D>) = 1 $ then it means that $L(D) = \varnothing$ so it implies that $L(H)=\varnothing \,$ and we have a contradiction because $H$ accepts $<D>$. And another contradiction will arise if $ H(<D>) = 0 $.