Un llenguatge s'anomena Decidible o Recursiu si hi ha una màquina Turing que accepta i s'atura en cada cadena d'entrada w. Cada idioma decidible és Turing-Acceptable. Un problema de decisió P és decidible si el llenguatge L de totes les instàncies sí a P és decidible.
Què vols dir amb Decidabilitat?
: capaç de decidir-se específicament: capaç de decidir-se com a conseqüència o no dels axiomes d'un sistema lògic La lògica era completa…? I era decidible, en el sentit que hi havia un mètode que demostrava la veritat o la falsedat de cada afirmació? -
Quina diferència hi ha entre la decidibilitat i la indecidència?
A problema de decisió es pot decidir si hi ha un algorisme de decisió per a això. En cas contrari és indecidible. Per demostrar que un problema de decisió és decidible, n'hi ha prou amb donar-hi un algorisme.
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ó).
Què és el problema de la determinabilitat?
(definició) Definició: Un problema de decisió que es pot resoldre mitjançant un algorisme que s'atura en totes les entrades en un nombre finit de passos El llenguatge associat s'anomena llenguatge decidible. També conegut com a problema totalment decidible, solucionable algorítmicament, solucionable recursivament.
