semi-decidable

adjective

Of a set, such that there is a deterministic algorithm such that (a) if an element is a member of the set, the algorithm halts with the result "positive", and (b) if an element is not a member of the set, (i) the algorithm does not halt, or (ii) if it does, then with the result "negative".

Similar
recursively enumerable
OriginEnglish decidable ← Latin sēmi- ← Proto-Indo-European *sēmi →
Ask AI about this wordChatGPTClaudePerplexityGoogle AIGrok

Meanings

adjectivesemi-decidable (not comparable)

alternative semidecidable

  1. not comparablecomputingOf a set, such that there is a deterministic algorithm such that (a) if an element is a member of the set, the algorithm halts with the result "positive", and (b) if an element is not a member of the set, (i) the algorithm does not halt, or (ii) if it does, then with the result "negative".

    Synonyms: recursively enumerable

Synonyms & antonyms

adjectiveOf a set, such that there is a deterministic algorithm such that (a) if an element is a member of the set, the algorithm halts with the result "positive", and (b) if an element is not a member of the set, (i) the algorithm does not halt, or (ii) if it does, then with the result "negative".

Similar
recursively enumerable

Origin

  1. Proto-Indo-European*sem-
  2. Proto-Indo-European*sēmi
  3. Latinsēmi-
  4. Englishsemi-
  5. Englishdecidable
  6. Englishsemi-decidable

From semi- + decidable.

Full word history & related roots →
Cite this entry
APA

semi-decidable. (n.d.). In WatkinsX Dictionary. Retrieved November 2, 2026, from https://dictionary.watkinsx.com/word/semi-decidable

MLA

“semi-decidable.” WatkinsX Dictionary, https://dictionary.watkinsx.com/word/semi-decidable. Accessed November 2, 2026.

Chicago

WatkinsX Dictionary, s.v. “semi-decidable,” accessed November 2, 2026, https://dictionary.watkinsx.com/word/semi-decidable.

Source: semi-decidable on Wiktionary, CC BY-SA 4.0.