減少以補充接受問題


2

我正在將給定的圖靈機減少到已知的不確定問題的補充,$$ Complement(A_ {TM})= \ {\ langle M,w \ rangle \ mid M \ text {is TM},w \ not \ in L(M)\} $$

對於這台名為SPARSE TM的圖靈機:$$SPARSE_ {TM} = \ {\ langle M \ rangle \ mid M \ text {是1-tape TM},| L(M)|\ leq 1000 \}$$

到目前為止,這裡是我所擁有的,但是我認為我需要幫助,因為我發表的其中一項陳述似乎有些可疑。

假定有一個TM S決定接受TM的補碼,一個TM R決定稀疏。然後S看起來像:

S = "On input `<M,w>`:
    Construct M':
        M' = "On input x:
            if x in L(M):  #Fishy statement
                accept
            else: reject
     Run R on <M'>
     if R accepts: accept; if R rejects: reject

這樣(如果正確的話)將減少SPARSE TM並證明它是不合格的,對嗎?任何幫助,將不勝感激。

2

When reducing $L_1$ to $L_2$, we need to come up with a computable mapping $f$ such that $x \in L_1$ iff $f(x) \in L_2$. We don't start with a Turing machine deciding $L_2$ and then construct one for deciding $L_1$, although this construction can easily be accomplished using the mapping $f$. The reason we refrain from doing so is that sometimes we already know that $L_2$ is undecidable, and yet there is merit in saying that $L_1$ reduces to $L_2$, since $L_1$ might have an even strong guarantee of "hardness"; this sort of thinking leads to classical recursion theory.

Regarding your construction, there are two problems: (1) it doesn't involve $w$, (2) when you write "if $x \in L(M)$", you actually mean "simulate $M$ on $x$"; this simulation could halt, or it could never halt. Generally speaking, when a Turing machine never halts, then we say that it rejects. See if this fits with what you were trying to accomplish.