– Er wordt gezegd dat een beslissingsprobleem P semi-beslisbaar is (d.w.z. een semi-algoritme heeft) als de taal L van alle ja-instanties tot P r.e. is. – (Equivalentieprobleem voor DFA) Accepteren ze, gegeven twee DFA's, dezelfde taal? Bewijs: Denk aan Cantors argument uit de eerste lezing.
Wanneer wordt gezegd dat een probleem semi-beslisbaar is?
Semi-beslisbare problemen zijn die voor waarbij een Turing-machine stopt op de invoer die door hem wordt geaccepteerd, maar het kan stoppen of voor altijd herhalen op de invoer die wordt afgewezen door de Turing Machine. Dergelijke problemen worden Turing-herkenbare problemen genoemd.
Wat is een gedeeltelijk beslisbaar probleem?
Definitie: Een waarvan de bijbehorende taal een recursief opsombare taal is. Op equivalente wijze bestaat er een algoritme dat stopt en 1 uitvoert voor elke instantie die een "ja" antwoord heeft, maar voor instanties die een "nee" antwoord hebben, is het toegestaan om ofwel niet te stoppen of te stoppen en 0 uit te voeren.
Is het stoppen van het probleem gedeeltelijk beslisbaar?
Alan Turing bewees in 1936 dat een algemeen algoritme dat op een Turing-machine draait en dat het stopprobleem voor alle mogelijke programma-invoerparen oplost, niet noodzakelijkerwijs kan bestaan. Daarom is het stopprobleem onbeslisbaar voor Turingmachines.
Waarom is het stopprobleem semi-beslisbaar?
Er wordt gezegd dat een taal Semi-beslisbaar is als er een Turing-machine bestaat die staakt als een woord tot de taal behoort (JA-gevallen) en kan worden afgewezen of oneindig wordt loop als het woord niet bij de taal hoort (GEEN hoofdlettergebruik).
