Per demostrar que un idioma és decidible, necessitem per crear una màquina de Turing que s'aturarà en qualsevol cadena d'entrada de l'alfabet de l'idioma. Com que M és un dfa, ja tenim la màquina de Turing i només hem de demostrar que el dfa s'atura a cada entrada.
Com es calcula la decidibilitat?
Un idioma és decidible si i només si ell i el seu complement són reconeixibles. Prova. Si una llengua és decidible, llavors el seu complement és decidible (per tancament sota complementació).
Com demostres la decisió de Turing?
Proveu que l'idioma que reconeix és igual a l'idioma donat i que l'algorisme s'atura en totes les entrades. Per demostrar que un llenguatge donat és reconeixible per Turing: Construeix un algorisme que accepti exactament aquelles cadenes que estan en l'idiomaHa de rebutjar o fer un bucle en qualsevol cadena que no estigui en l'idioma.
Com saps si un idioma és reconeixible?
Un llenguatge L es pot reconèixer si i només si existeix un verificador per a L, on un verificador és una màquina de Turing que s'atura en totes les entrades i per a tots els w∈Σ∗, w∈L↔∃c∈Σ∗. V accepta ⟨w, c⟩.
Com demostres que un problema és indecidible?
El problema de la totalitat és indecidible
El problema d'aturada es pot utilitzar per demostrar que altres problemes són indecidibles. Problema de totalitat: Es diu que una funció (o programa) F és total si es defineix F(x) per a tots els x (o de manera similar, si F(x) s'atura per a tots els x). Determinar si una funció F és total o no és indecidible.
