Prove que REGULAR_TM é indecidível

Estou estudando a prova do seguinte teorema:

Dada a linguagem

$\mathit{REGULAR}_\mathit{TM} = \{\langle M \rangle | M$ é uma máquina de turing e $\mathit{Accept}(M)$ é regular$\}$

$\mathit{REGULAR}_\mathit{TM}$ é indecidível.

A prova dada na Sipser mostra que, se já temos uma máquina $R$ que decide $\mathit{REGULAR}_\mathit{TM}$ então nós podemos fazer uma máquina $S$ que decide o problema da parada:

Estou tendo problemas para entender a prova. Aqui está como eu o entendo:

Quando $M$ (qualquer máquina de turing) e $w$ (qualquer fio) é alimentado na máquina $S$, construímos uma máquina $M_2$ que pega uma corda $x$ como entrada, mas primeiro executa a máquina $M$ em $w$. Primeiro caso, se$w$ $\in$$\mathit{Accept}(M)$, então $M_2$simplesmente aceita x. Isso é$\mathit{Accept}(M_2) = \sum^*$neste caso - ou seja, um idioma comum. Caso contrário, segundo caso,$M$ rejeita $w$, então $M_2$ verifica se a entrada $x$ é da forma $0^n1^n$e aceita se é assim - ou seja, $\mathit{Accept}(M_2)$não é uma linguagem comum. Dentro$S$, nos dois casos, se executarmos $R$ em $M_2$ retorna o resultado apropriado que $S$ pode retornar diretamente.

O caso sobre o qual estou confuso, o terceiro caso, é quando $M$ não pára $w$. Então$\mathit{Accept}(M_2) = \{\}$, que é um idioma comum e $R$retornará , portanto , ACEITAR , que$S$ não pode retornar diretamente como $w \notin \mathit{Accept}(M)$. Mas a descrição da solução me soa como$S$retorna ACEITAR mesmo neste caso (pseudocódigo abaixo). Então, o que estou fazendo de errado? Provavelmente, estou perdendo uma ideia muito básica. Aqui está o pseudocódigo da máquina$S$e dentro $S$, como você pode ver, existe a máquina $M_2$ aquele $S$ cria.

machine S(M, w):
    // Construct an instance of machine M2 which uses M and w
    machine M2(x):
        r := M(w)  // Might hang here
        if r == ACCEPT:
            return ACCEPT
        else:
            if x is of form 0^n.1^n:
                return ACCEPT
            else:
                return REJECT

    // Run R on M2 (always returns, never hangs)
    r1 = R(M2)
    if r1 == ACCEPT:
        return ACCEPT
    else:
        return REJECT

Procure o teorem de Rice. Sua prova é bastante curta e doce. Ele diz que qualquer propriedade não trivial de uma linguagem da MT (ou seja, uma que nem todos os idiomas da TM compartilham) é indecidível, no sentido de que não pode ser decidido olhando para a TM se o idioma que ela aceita possui a propriedade.

A propriedade de ser regular (ou um idioma livre de contexto, ou o idioma vazio, ou o idioma de todas as strings, ou ...) não é trivial; portanto, se uma TM específica aceita um idioma com a propriedade, é indecidível, por Rice teorema.

Seu pseudocódigo está errado, o seguinte é o correto:

machine S(M, w):
    // Construct an instance of machine M2 which uses M and w
    machine M2(x):
        if x is of form 0^n.1^n:
            return ACCEPT
        else:
            r := M(w) // If LOOP, M2 accept 0^n.1^n
            if r == ACCEPT: 
                return ACCEPT // M2 accept Sigma* (Only this case make M2 accept regular language if only if M(w) accept)
            else if r == REJECT: 
                return REJECT // M2 accept 0^n.1^n

    // Run R on M2 (always returns, never hangs)
    r1 = R(M2)
    if r1 == ACCEPT:
        return ACCEPT
    else:
        return REJECT

@ David Richerby Aqui está mais explicação:

1. vonbrand está certo
   Ele usou o teorema de Rice, diz que qualquer propriedade não trivial de uma linguagem da MT é indecidível. Tudo bem, mas ... no livro de Sipser, este exemplo é para demonstrar o mapeamento da redutibilidade.
   Portanto, devemos usar a redução para resolver esse problema, em vez do teorem de Rice.

2. O que há de errado com a resposta proposta?
   O errado é:
   Quando M (w) LOOP em M2, R (M2) retornará ACEITAR. Por quê? Como nesse caso L (M2) é {}, que é um idioma normal. Mas quando M (w) LOOP, R (M2) não deve retornar ACEITAR.
   Imagine:
   Se R (M2) retornar ACEITAR, o que acontecerá?
   Haverá duas possibilidades para M2 fazer com que R (M2) aceite.
   (1) M (w) retorna ACEITAR.
   (2) M (w) LOOP.
   Obviamente, "duas possibilidades" não atende à definição de redução.
   Qual é a definição de Redução?

   Observe <=>, que é "se apenas se".

3. O que minha resposta faz para corrigi-la?
   O principal é: existe apenas uma possibilidade para M2 fazer R (M2) aceitar, que é M (w) retornar ACEITAR! Que atendem à definição de redução.

4. Outra solução para esse problema:

   machine S(M, w):
       // Construct an instance of machine M2 which uses M and w
       machine M2(x):
           r := M(w)
           if r == ACCEPT:
               if x is of form 0^n.1^n:
                   return ACCEPT
               else:
                   return REJECT
           else if r == REJECT:
               return REJECT
   
       // Run R on M2 (always returns, never hangs)
       r1 = ComplementOfR(M2) // use Complement Of R
       if r1 == ACCEPT:
           return REJECT
       else:
           return ACCEPT
   

   Nesta solução, uso ComplementOfR em vez de R.
   Os benefícios disso são:
   Agora, em M2, podemos executar M em w primeiro.
   Por que podemos usar ComplementOfR?
   Se R é decidível, ComplementOfR também é decidível. Assim, podemos usar ComplementOfR.