semi-decidable
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".

Wikipedia foundation.

Look at other dictionaries:

  • Langage partiellement décidable — Récursivement énumérable En théorie de la calculabilité, un ensemble récursivement énumérable ou semi décidable est un ensemble qui est le domaine de définition, ou, de façon équivalente, l image d un fonction calculable (il faut ajouter l… …   Wikipédia en Français

  • LOGIQUE MATHÉMATIQUE — La logique au sens étroit du terme, c’est à dire la logique formelle par opposition à l’épistémologie ou à la théorie de la connaissance, se propose de donner une théorie de l’inférence formellement valide. Elle considère comme valide toute… …   Encyclopédie Universelle

  • Théorème de Rice — En théorie de la calculabilité, le théorème de Rice dit que toute propriété non triviale (c’est à dire qui n est pas toujours vraie ou toujours fausse) sur la sémantique dénotationnelle d un langage de programmation Turing complet est indécidable …   Wikipédia en Français

  • Théorème de rice — En théorie de la calculabilité, le théorème de Rice dit que toute propriété non triviale (c’est à dire qui n est pas toujours vraie ou toujours fausse) sur la sémantique dénotationnelle d un langage de programmation Turing complet est indécidable …   Wikipédia en Français

  • RÉCURSIVITÉ — Les (semi ) fonctions récursives ont été introduites pour donner un équivalent mathématique à la notion métamathématique intuitive de (semi ) fonction effectivement ou mécaniquement calculable (cf. LOGIQUE MATHÉMATIQUE, chap. 4). Par souci de… …   Encyclopédie Universelle

  • Decidability (logic) — In logic, the term decidable refers to the decision problem, the question of the existence of an effective method for determining membership in a set of formulas. Logical systems such as propositional logic are decidable if membership in their… …   Wikipedia

  • Calcul Des Prédicats — Le calcul des prédicats du premier ordre, ou calcul des relations, ou logique du premier ordre, ou tout simplement calcul des prédicats est une formalisation du langage des mathématiques proposée par les logiciens de la fin du XIXe siècle et …   Wikipédia en Français

  • Calcul des predicats — Calcul des prédicats Le calcul des prédicats du premier ordre, ou calcul des relations, ou logique du premier ordre, ou tout simplement calcul des prédicats est une formalisation du langage des mathématiques proposée par les logiciens de la fin… …   Wikipédia en Français

  • Calcul des prédicats — Le calcul des prédicats du premier ordre, ou calcul des relations, ou logique du premier ordre, ou tout simplement calcul des prédicats est une formalisation du langage des mathématiques proposée par les logiciens de la fin du XIXe siècle et …   Wikipédia en Français

  • Calcul des prédicats du premier ordre — Calcul des prédicats Le calcul des prédicats du premier ordre, ou calcul des relations, ou logique du premier ordre, ou tout simplement calcul des prédicats est une formalisation du langage des mathématiques proposée par les logiciens de la fin… …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”