| dbo:abstract
|
- La terminaison est une propriété fondamentale des algorithmes. Elle stipule que les calculs décrits par l'algorithme s'arrêteront. En général cet arrêt doit avoir lieu quelles que soient les données initiales que l'on fournit à l'algorithme. Si l'on veut insister sur ce point on parle alors souvent de terminaison uniforme, mais le plus généralement « terminaison » couvre aussi bien l'arrêt sur une donnée que l'arrêt sur toutes les données et c'est le contexte qui décide. La terminaison forme avec la correction partielle un des aspects de la correction des algorithmes, la correction partielle et la terminaison forment ce que l'on appelle la correction totale. Dans le cas spécifique des machines de Turing, la terminaison s'appelle l'arrêt (halting en anglais dans le vocabulaire de Turing). Un cas particulier d'étude de la terminaison est la terminaison d'un système de réécriture. (fr)
- In computer science, termination analysis is program analysis which attempts to determine whether the evaluation of a given program halts for each input. This means to determine whether the input program computes a total function. It is closely related to the halting problem, which is to determine whether a given program halts for a given input and which is undecidable. The termination analysis is even more difficult than the Halting problem: the termination analysis in the model of Turing machines as the model of programs implementing computable functions would have the goal of deciding whether a given Turing machine is a total Turing machine, and this problem is at level of the arithmetical hierarchy and thus is strictly more difficult than the Halting problem. Now as the question whether a computable function is total is not semi-decidable, each sound termination analyzer (i.e. an affirmative answer is never given for a non-terminating program) is incomplete, i.e. must fail in determining termination for infinitely many terminating programs, either by running forever or halting with an indefinite answer. (en)
|
| dbo:wikiPageExternalLink
| |
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 16009 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| dbp:wikiPageUsesTemplate
| |
| dcterms:subject
| |
| gold:hypernym
| |
| rdf:type
| |
| rdfs:comment
|
- La terminaison est une propriété fondamentale des algorithmes. Elle stipule que les calculs décrits par l'algorithme s'arrêteront. En général cet arrêt doit avoir lieu quelles que soient les données initiales que l'on fournit à l'algorithme. Si l'on veut insister sur ce point on parle alors souvent de terminaison uniforme, mais le plus généralement « terminaison » couvre aussi bien l'arrêt sur une donnée que l'arrêt sur toutes les données et c'est le contexte qui décide. La terminaison forme avec la correction partielle un des aspects de la correction des algorithmes, la correction partielle et la terminaison forment ce que l'on appelle la correction totale. (fr)
- In computer science, termination analysis is program analysis which attempts to determine whether the evaluation of a given program halts for each input. This means to determine whether the input program computes a total function. Now as the question whether a computable function is total is not semi-decidable, each sound termination analyzer (i.e. an affirmative answer is never given for a non-terminating program) is incomplete, i.e. must fail in determining termination for infinitely many terminating programs, either by running forever or halting with an indefinite answer. (en)
|
| rdfs:label
|
- Terminaison d'un algorithme (fr)
- Termination analysis (en)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:knownFor
of | |
| is dbo:wikiPageDisambiguates
of | |
| is dbo:wikiPageRedirects
of | |
| is dbo:wikiPageWikiLink
of | |
| is dbp:knownFor
of | |
| is rdfs:seeAlso
of | |
| is foaf:primaryTopic
of | |
