證明語言的長度除以2是不可判定的

Question

如何證明使用語言長度除以2的約簡方法？ L = {|是一個圖靈機，其中| L（M）| = 0模2}

我有2個想法，但我害怕跟錯了一個 1）我用Amt的還原方法，我說圖靈機將x = w0 ..... wi作爲輸入並且當且僅當wi = 0 mod 2時才接受。

2）我使用NOT HALT的還原方法，我說圖靈機會拒絕任何輸入，所以圖靈機的長度將爲0，這就滿足了上面的條件！

有何建議？

Answer 1

這裏有一個選項。給定一個TM M和串瓦特，建立這個新TM N：

N = "On input x: 
     If x isn't the empty string, reject. 
     Otherwise, run M on w. 
     If M accepts, accept; if M rejects, reject. 
     (Implicitly, if M loops on w, N loops on x.)" 

這TM具有這樣的特性，如果M接受瓦特，則L（N）= {＆小量;}，所以| L（N） | = 1。否則，如果M不接受w，則L（N）=＆emptyset ;,所以| L（N）| = 0.

看看你是否可以在減少中使用它。

這裏有其他兩種方法，你可以採取：

1. 應用Rice's theorem立即得出結論，這種語言是不可判定的，因爲詢問是否| L（M）|甚至是RE語言的一個不平凡的屬性。
2. 使用Recursion Theorem：構建一個TM，詢問其語言是否包含偶數個字符串，如果答案爲「是」則選擇不接受，如果答案爲「否」，則選擇接受空字符串。這個TM的語言如果並且只有它沒有 - 纔是矛盾的！