retagged by
522 views
0 votes
0 votes

Here are two definitions of languages that are similar to the definition of $L_{d}$, yet different from that language. For each, show that the language is not accepted by a Turing machine, using a diagonalization-type argument. Note that you cannot develop an argument based on the diagonal itself, but must find another infinite sequence of points in  the matrix suggested by Fig.$9.1$.

  1. The set of all $w_{i}$ such that $w_{i}$ is not accepted by $M_{2i}$.  
  2. The set of all $w_{i}$ such that $w_{2i}$ is not accepted by $M_{i}$.
retagged by

Please log in or register to answer this question.

Related questions

0 votes
0 votes
0 answers
1
admin asked Jul 21, 2019
399 views
Write one of the possible codes for the Turing machine of Fig.$8.9.$
0 votes
0 votes
0 answers
2
admin asked Jul 21, 2019
310 views
Show that the set of Turing-machine codes for TM's that accept all inputs that are palindromes (possibly along with some other inputs) is undecidable.
0 votes
0 votes
0 answers
4