圖靈機的可判定性正好接受14個單詞


2

您是否會說以下問題無法確定? $$ L_1 = \ {\ langle T \ rangle \ mid T \ text {接受14個單詞} \} $$ 我的直覺說,這一定是無法確定的,我想盡力減少圖靈機的空度問題。如果我們可以判斷一個TM是否接受14個單詞,那麼我們應該能夠知道它是否接受0個單詞。由於我們知道EMPT是無法確定的,因此我一直在嘗試將EMPT減少到這個問題,但是我不確定怎麼做。

任何人都可以確認這實際上是否是一個有效的起點,如果是,那麼是否有任何關於製定正式減價的提示?

1

Your intuition is correct. Probably you can reduce emptiness (or maybe its complement) to this language but it's not the way I'd do it. Instead, think about how you prove that emptiness is undecidable.

You want to know if $M$ halts on input $w$ so you produce a TM that accepts everything if $M$ accepts $w$ and rejects everything if $M$ rejects $w$. A slight modification of that proof will show that your language is undecidable.