[informatica teorica] Semidecidibilità

[lorenzo902]

Ho questo esercizio:
Let us consider a fixed character c. Prove that the problem of deciding whether or not a Turing Machine
prints c is semidecidable and not decidable.

So dimostrare che è indecidibile, ma come posso dimostrare la sua semidecidibilità?

Grazie

[xMauri94]

Così su due piedi è difficile rispondere, mi verrebbe un modo veramente banale per dimostrare che sia un problema semidecisionale, ma non so se può andarti bene..

Consideriamo la seguente funzione $f(x,y)$
\begin{cases} c \space se \space HALT(x,y) \\ \uparrow \space altrimenti \end{cases}
Sappiamo che: $HALT(x,y) \Leftrightarrow \Phi(x,y) \downarrow $

Dove $ \Phi $ è inteso come il programma universale.
Dove $x$ è un input qualsiasi e $y=#(P)$ è il numero di programma che calcola $f$. Quindi, sia $P$:

z1 <- Phi(x1,x2)
Y <- c

Assegno al valore di output $ Y $ il valore $ c $ se e solo se il programma non si ferma. Ma se $\neg HALT(x,y)$ il programma diverge.

Questa $ f$ dovrebbe mostrare la funzione richiesta.

[lorenzo902]

Grazie