Kleene's recursion theorem (original) (raw)
Die Rekursionssätze sind drei Resultate der Theoretischen Informatik, genauer der Berechenbarkeitstheorie, von Kleene, Rogers und Case.Sie beschreiben selbstreferenzielle Eigenschaften berechenbarer Funktionen.Dies wird durch algorithmische Modifikation natürlicher Zahlen erreicht, die einerseits als Codierungen von Programm-Quelltexten und andererseits als Funktionsargumente dienen.Trotz der sehr unterschiedlich gelagerten Aussagen sind alle drei Sätze formal äquivalent, aus jedem von ihnen lassen sich die jeweils anderen beiden herleiten.Die Rekursionssätze folgen allesamt aus dem Smn-Theorem, das ebenfalls zuerst von Kleene bewiesen wurde.
| Property | Value |
|---|---|
| dbo:abstract | Die Rekursionssätze sind drei Resultate der Theoretischen Informatik, genauer der Berechenbarkeitstheorie, von Kleene, Rogers und Case.Sie beschreiben selbstreferenzielle Eigenschaften berechenbarer Funktionen.Dies wird durch algorithmische Modifikation natürlicher Zahlen erreicht, die einerseits als Codierungen von Programm-Quelltexten und andererseits als Funktionsargumente dienen.Trotz der sehr unterschiedlich gelagerten Aussagen sind alle drei Sätze formal äquivalent, aus jedem von ihnen lassen sich die jeweils anderen beiden herleiten.Die Rekursionssätze folgen allesamt aus dem Smn-Theorem, das ebenfalls zuerst von Kleene bewiesen wurde. (de) In computability theory, Kleene's recursion theorems are a pair of fundamental results about the application of computable functions to their own descriptions. The theorems were first proved by Stephen Kleene in 1938 and appear in his 1952 book Introduction to Metamathematics. A related theorem, which constructs fixed points of a computable function, is known as Rogers's theorem and is due to Hartley Rogers, Jr. The recursion theorems can be applied to construct fixed points of certain operations on computable functions, to generate quines, and to construct functions defined via recursive definitions. (en) En théorie de la calculabilité, plusieurs théorèmes dus à Kleene sont appelés théorèmes de la récursion. Ils établissent l'existence de points fixes pour des transformateurs de programmes, au sens où le programme et le programme image calculent la même fonction partielle et ils sont nommés également théorèmes du point fixe de Kleene. Ils ont de nombreuses applications. (fr) Nella teoria della computabilità, i teoremi di ricorsione di Kleene sono due fondamentali risultati riguardanti l'applicazione di funzioni calcolabili a loro stesse. I teoremi furono dimostrati per la prima volta da Stephen Kleene nel 1938. I due teoremi di ricorsione possono essere applicati per costruire punti fissi di certe operazioni su funzioni calcolabili, per generare quine, e per costruire funzioni definite mediante definizione ricorsiva. (it) クリーネの再帰定理（クリーネのさいきていり、英: Kleene's recursion theorem）は、再帰理論における2つの基本的な結果である。この定理によれば計算可能関数をそれ自身を用いて記述することができる。この定理は1938年にスティーブン・コール・クリーネによって最初に証明された。1952年の彼の著作 Introduction to Metamathematics において見られる。 2つの再帰定理は幾つかの計算可能関数の不動点の構成に利用できる。例えばクワインの生成や関数の帰納的定義などである。任意の再帰的関数の不動点構成への応用はロジャースの定理として知られる。これは (Rogers, 1967) による。 (ja) Em teoria da computabilidade, o teorema da recursão de Kleene é um par de resultados fundamentais sobre a aplicação de funções computáveis para suas próprias descrições. Os teoremas foram inicialmente provados por Stephen Kleene em 1938. Os dois teoremas da recursão podem ser aplicados para construir pontos fixos de certas operações sobre funções computáveis, para gerar quines, e para construir funções definidas através de definições recursivas. (pt) |
| dbo:wikiPageExternalLink | https://archive.org/details/theoryofrecursiv00roge https://books.google.com/books%3Fid=KqeXZ4pPd5QC https://archive.org/details/BubliothecaMathematicaStephenColeKleeneIntroductionToMetamathematicsWoltersNoordhoffPublishing1971 |
| dbo:wikiPageID | 155407 (xsd:integer) |
| dbo:wikiPageLength | 19380 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1105394260 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Cambridge,_Massachusetts dbr:Enumeration_reducibility dbr:Hartley_Rogers,_Jr. dbr:North-Holland_Publishing dbr:Denotational_semantics dbr:Computability_theory dbr:Computable_function dbr:Order_theory dbr:Elsevier dbr:MIT_Press dbr:Stephen_Cole_Kleene dbr:Yury_Yershov dbr:Partial_function dbr:Admissible_numbering dbr:Fixed_point_(mathematics) dbc:Theorems_in_the_foundations_of_mathematics dbr:Diagonal_lemma dbr:Recursive_definition dbr:Quine_(computing) dbr:Recursively_enumerable dbr:Halting_problem dbr:Smn_theorem dbc:Computability_theory dbr:Lambda_calculus dbr:Piergiorgio_Odifreddi dbr:Reflection_(computer_programming) dbr:Kleene_fixed-point_theorem dbr:Turing_machine dbr:S-m-n_theorem dbr:Factorial dbr:Fixed-point_combinator dbr:M-recursive_function dbr:Lisp_programming_language dbr:Turing_degree dbr:The_Journal_of_Symbolic_Logic dbr:Partial_recursive_function dbr:Gödel_number dbr:Kleene's_theorem dbr:Precomplete_numbering |
| dbp:wikiPageUsesTemplate | dbt:Cite_book dbt:Cite_journal dbt:Distinguish dbt:R dbt:Reflist dbt:Sfn dbt:SEP dbt:Use_shortened_footnotes |
| dct:subject | dbc:Theorems_in_the_foundations_of_mathematics dbc:Computability_theory |
| gold:hypernym | dbr:Pair |
| rdf:type | owl:Thing dbo:Place yago:WikicatMathematicalTheorems yago:WikicatTheorems yago:WikicatTheoremsInTheFoundationsOfMathematics yago:Abstraction100002137 yago:Communication100033020 yago:Message106598915 yago:Proposition106750804 yago:Statement106722453 yago:Theorem106752293 |
| rdfs:comment | Die Rekursionssätze sind drei Resultate der Theoretischen Informatik, genauer der Berechenbarkeitstheorie, von Kleene, Rogers und Case.Sie beschreiben selbstreferenzielle Eigenschaften berechenbarer Funktionen.Dies wird durch algorithmische Modifikation natürlicher Zahlen erreicht, die einerseits als Codierungen von Programm-Quelltexten und andererseits als Funktionsargumente dienen.Trotz der sehr unterschiedlich gelagerten Aussagen sind alle drei Sätze formal äquivalent, aus jedem von ihnen lassen sich die jeweils anderen beiden herleiten.Die Rekursionssätze folgen allesamt aus dem Smn-Theorem, das ebenfalls zuerst von Kleene bewiesen wurde. (de) En théorie de la calculabilité, plusieurs théorèmes dus à Kleene sont appelés théorèmes de la récursion. Ils établissent l'existence de points fixes pour des transformateurs de programmes, au sens où le programme et le programme image calculent la même fonction partielle et ils sont nommés également théorèmes du point fixe de Kleene. Ils ont de nombreuses applications. (fr) Nella teoria della computabilità, i teoremi di ricorsione di Kleene sono due fondamentali risultati riguardanti l'applicazione di funzioni calcolabili a loro stesse. I teoremi furono dimostrati per la prima volta da Stephen Kleene nel 1938. I due teoremi di ricorsione possono essere applicati per costruire punti fissi di certe operazioni su funzioni calcolabili, per generare quine, e per costruire funzioni definite mediante definizione ricorsiva. (it) クリーネの再帰定理（クリーネのさいきていり、英: Kleene's recursion theorem）は、再帰理論における2つの基本的な結果である。この定理によれば計算可能関数をそれ自身を用いて記述することができる。この定理は1938年にスティーブン・コール・クリーネによって最初に証明された。1952年の彼の著作 Introduction to Metamathematics において見られる。 2つの再帰定理は幾つかの計算可能関数の不動点の構成に利用できる。例えばクワインの生成や関数の帰納的定義などである。任意の再帰的関数の不動点構成への応用はロジャースの定理として知られる。これは (Rogers, 1967) による。 (ja) Em teoria da computabilidade, o teorema da recursão de Kleene é um par de resultados fundamentais sobre a aplicação de funções computáveis para suas próprias descrições. Os teoremas foram inicialmente provados por Stephen Kleene em 1938. Os dois teoremas da recursão podem ser aplicados para construir pontos fixos de certas operações sobre funções computáveis, para gerar quines, e para construir funções definidas através de definições recursivas. (pt) In computability theory, Kleene's recursion theorems are a pair of fundamental results about the application of computable functions to their own descriptions. The theorems were first proved by Stephen Kleene in 1938 and appear in his 1952 book Introduction to Metamathematics. A related theorem, which constructs fixed points of a computable function, is known as Rogers's theorem and is due to Hartley Rogers, Jr. (en) |
| rdfs:label | Rekursionssatz (de) Théorème de récursion de Kleene (fr) Kleene's recursion theorem (en) Teorema di ricorsione di Kleene (it) クリーネの再帰定理 (ja) Teorema da recursividade de Kleene (pt) |
| owl:sameAs | freebase:Kleene's recursion theorem yago-res:Kleene's recursion theorem wikidata:Kleene's recursion theorem dbpedia-de:Kleene's recursion theorem dbpedia-fr:Kleene's recursion theorem dbpedia-he:Kleene's recursion theorem dbpedia-it:Kleene's recursion theorem dbpedia-ja:Kleene's recursion theorem dbpedia-la:Kleene's recursion theorem dbpedia-pt:Kleene's recursion theorem dbpedia-th:Kleene's recursion theorem https://global.dbpedia.org/id/r6g1 |
| prov:wasDerivedFrom | wikipedia-en:Kleene's_recursion_theorem?oldid=1105394260&ns=0 |
| foaf:isPrimaryTopicOf | wikipedia-en:Kleene's_recursion_theorem |
| is dbo:wikiPageDisambiguates of | dbr:Recursion_theorem |
| is dbo:wikiPageRedirects of | dbr:Kleene_Recursion_Theorem dbr:Kleene_Recursion_theorem dbr:Kleene_recursion_theorem |
| is dbo:wikiPageWikiLink of | dbr:Enumeration_reducibility dbr:Decider_(Turing_machine) dbr:Reverse_mathematics dbr:List_of_mathematical_logic_topics dbr:Stephen_Cole_Kleene dbr:Complete_numbering dbr:Functional_programming dbr:John_Darlington dbr:Diagonal_lemma dbr:Quine_(computing) dbr:Recursion_theorem dbr:Smn_theorem dbr:Diagonal_argument dbr:List_of_theorems dbr:Fixed-point_theorems dbr:Rice's_theorem dbr:Kleene_Recursion_Theorem dbr:Kleene_Recursion_theorem dbr:Kleene_recursion_theorem |
| is foaf:primaryTopic of | wikipedia-en:Kleene's_recursion_theorem |