Semidecideerbaar

Semidecideerbaar is een term uit de computability-theorie die betrekking heeft op beslissingsproblemen of talen. Een taal L ⊆ Σ* is semidecideerbaar als er een Turing-machine M bestaat die voor elke invoer w het volgende doet: als w ∈ L, stopt M en accepteert; als w ∉ L, stopt M niet (kan oneindig blijven draaien). In andere woorden: er bestaat een procedure die ja-instances accepteert, terwijl sommige nee-instances mogelijk nooit opgelost worden.

Een equivalente benadering is dat L effectief kan worden opgenoemd of gedefinieerd als een recursief op te sommen (recursively enumerable) taal: er bestaat een machine die alle elementen van L in some volgorde kan opsommen. Deze twee definities sluiten elkaar naadloos uit: een semidecideerbare taal is r.e., en omgekeerd kan een r.e. taal worden gegenereerd door een opnoemende procedure.

Relatie met beslisbaarheid: als zowel een taal L als zijn complement L^c semidecideerbaar zijn, dan is L decidabel. Alle decidabele talen zijn automatisch semidecideerbaar, maar niet elke semidecideerbare taal is decidabel. Een klassieke illustratie is het Halting-probleem HALT = {⟨M, w⟩ | M stopt op invoer w}, dat semidecideerbaar is door simulatie van M op w; het complement van HALT is daarentegen niet semidecideerbaar.

Zie ook termen als recursief op te sommen (r.e.), herkenbare talen en co-rekenbare talen (co-r.e.). Semidecideerbaar wordt vaak toegepast in discussies over wat er effectief kan worden vastgesteld in computermachines en wat niet.