M машина Тьюринга, которая принимает строку ж и не принимает строку ε

Question

мне нужно доказать, является ли этот язык узнаваем или нет:

{& Лангле; M, W & rangle ;: M машина Тьюринга, которая принимает строку ж и не принимает строку е}

Я полагаю, что я мог бы сделать сокращение на A _TM, но как я могу справиться с пустой строкой?

Answer 1

Это один из способов сделать редукцию из слова A _TM на ваш язык.

Учитывая TM M и строку ж, построить этот TM/струнный пары:

M' = "On input x: 
     If x = "iheartquokkas", accept. 
     Otherwise: 
      Run M on w. 
      If M accepts, accept; 
      If M rejects, reject; 
      (Implicitly: if M loops, loop.)" 
w' = "iheartquokkas" 

Предположим сначала, что M не принимает вес. Тогда машина M 'действительно принимает строку w', потому что она запрограммирована на это. Кроме того, когда вы запускаете M 'on & epsilon ;, он будет запускать M на w и никогда не будет принимать, потому что M не принимает w. Таким образом, M 'принимает w', но не & epsilon ;, поэтому & langle; M ', w' & rangle; на вашем языке.

Во-вторых, предположим, что M принимает w. Затем, когда вы запустите M 'on & epsilon ;, он примет, поэтому не так, M' принимает w ', но не & epsilon ;. Следовательно, & langle; M ', w' & rangle; не на вашем языке.

Теперь у вас есть сокращение отображения от A _{Дополнение TM} к вашему языку, поэтому ваш язык не узнаваем.

Теперь, вы можете доказать, что это не узнаваемо?