Numbering (computability theory) (original) (raw)
Eine Nummerierung einer Menge , im Sinne der Berechenbarkeitstheorie, ist eine möglicherweise partielle surjektive Funktion . Nummerierungen und die verwandten Notationen sind z. B. Werkzeuge beim Beweis der Äquivalenz von Register- und Turingmaschinen. Wenn die Zuordnung berechenbar ist, spricht man auch von einer effektiven Nummerierung.
| Property | Value |
|---|---|
| dbo:abstract | Eine Nummerierung einer Menge , im Sinne der Berechenbarkeitstheorie, ist eine möglicherweise partielle surjektive Funktion . Nummerierungen und die verwandten Notationen sind z. B. Werkzeuge beim Beweis der Äquivalenz von Register- und Turingmaschinen. Wenn die Zuordnung berechenbar ist, spricht man auch von einer effektiven Nummerierung. (de) La numération désigne le mode de représentation des nombres, et peut éventuellement se restreindre aux ordinaux ou cardinaux, ou à un ou plusieurs ensembles de nombres donnés. Cette représentation peut être concrète et matérielle, ou, au contraire, abstraite, par le biais des mots, gestes et signes qui ont permis aux différents peuples d'énoncer, de mimer et d'écrire ces nombres. De façon plus spécifique, la numération peut désigner un mode de représentation des nombres lié à un système d’écriture en chiffres précis. Aujourd'hui la numération occidentale, dite « arabe » ou « indo-arabe », à la fois décimale et positionnelle, tend à s'imposer dans le monde. (fr) In computability theory a numbering is the assignment of natural numbers to a set of objects such as functions, rational numbers, graphs, or words in some formal language. A numbering can be used to transfer the idea of computability and related concepts, which are originally defined on the natural numbers using computable functions, to these different types of objects. Common examples of numberings include Gödel numberings in first-order logic, the description numbers that arise from universal Turing machines and admissible numberings of the set of partial computable functions. (en) ナンバリング（英: numbering）は自然数から対象の集合への対応付けをいう。対象としては例えば関数、有理数、グラフ、形式言語などである。ナンバリングは自然数に対して定義された計算可能性や関連する概念を他の種類の対象に一般化する際に用いることができる。 よく知られた例としては一階述語論理のゲーデル数化や部分計算可能関数のがある。 (ja) Na teoria da computabilidade, numeração é a atribuição de números naturais para um conjunto de objetos como números racionais, gráficos ou palavras em alguma linguagem. A numeração pode ser usada para transferir a idéia de computabilidade e conceitos relacionados, que estão estritamente definidos sobre os números naturais usando funções computáveis, para objetos diferentes. Numerações importantes são a numeração de Gödel dos termos de lógica de primeira ordem (LPO) e numerações do conjunto de funções computáveis, que pode ser usado para aplicar os resultados da teoria da computabilidade sobre o conjunto de funções computáveis em si. (pt) В теорії обчислень нумерація - це присвоєння натуральних номерів множині об'єктів таких як раціональні числа, графи, чи слова в деякій мові. Нумерації можуть використовуватись для передачі поняття обчислюваності і пов'язаних з нею, які формально означені на натуральних числах за допомогою обчислюваних функцій, на ширші класи об'єктів. (uk) 可計算性理論裡，編號（英語：numbering、indexing等）是將一個集合的元素（如函數、有理數、圖、或形式語言的字串）編上自然數號碼。可計算性以及相關的概念最先定義在自然數上，而利用編號，可將這些概念傳遞到上述的其他集合中作討論。 常見例子有一階邏輯的哥德爾編號以及偏可計算函數的。 (zh) |
| dbo:wikiPageID | 2399097 (xsd:integer) |
| dbo:wikiPageLength | 4822 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1075402104 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Preorder dbr:Cylindrification dbr:Vladimir_Andreyevich_Uspensky dbr:Description_number dbr:Computability_theory dbr:Computable_function dbr:Function_(mathematics) dbr:Graph_(discrete_mathematics) dbr:Complete_numbering dbr:Friedberg_numbering dbr:Partial_function dbr:Admissible_numbering dbr:Gödel_numbering dbr:First-order_logic dbr:Formal_language dbr:Recursively_enumerable dbc:Computability_theory dbc:Theory_of_computation dbr:Surjective_function dbr:Domain_(function) dbr:Natural_number dbr:Rational_number dbr:Recursively_enumerable_set dbr:Set_(mathematics) dbr:Universal_Turing_machine dbr:Yuri_Ershov |
| dbp:wikiPageUsesTemplate | dbt:Reflist |
| dct:subject | dbc:Computability_theory dbc:Theory_of_computation |
| gold:hypernym | dbr:Assignment |
| rdfs:comment | Eine Nummerierung einer Menge , im Sinne der Berechenbarkeitstheorie, ist eine möglicherweise partielle surjektive Funktion . Nummerierungen und die verwandten Notationen sind z. B. Werkzeuge beim Beweis der Äquivalenz von Register- und Turingmaschinen. Wenn die Zuordnung berechenbar ist, spricht man auch von einer effektiven Nummerierung. (de) La numération désigne le mode de représentation des nombres, et peut éventuellement se restreindre aux ordinaux ou cardinaux, ou à un ou plusieurs ensembles de nombres donnés. Cette représentation peut être concrète et matérielle, ou, au contraire, abstraite, par le biais des mots, gestes et signes qui ont permis aux différents peuples d'énoncer, de mimer et d'écrire ces nombres. De façon plus spécifique, la numération peut désigner un mode de représentation des nombres lié à un système d’écriture en chiffres précis. Aujourd'hui la numération occidentale, dite « arabe » ou « indo-arabe », à la fois décimale et positionnelle, tend à s'imposer dans le monde. (fr) In computability theory a numbering is the assignment of natural numbers to a set of objects such as functions, rational numbers, graphs, or words in some formal language. A numbering can be used to transfer the idea of computability and related concepts, which are originally defined on the natural numbers using computable functions, to these different types of objects. Common examples of numberings include Gödel numberings in first-order logic, the description numbers that arise from universal Turing machines and admissible numberings of the set of partial computable functions. (en) ナンバリング（英: numbering）は自然数から対象の集合への対応付けをいう。対象としては例えば関数、有理数、グラフ、形式言語などである。ナンバリングは自然数に対して定義された計算可能性や関連する概念を他の種類の対象に一般化する際に用いることができる。 よく知られた例としては一階述語論理のゲーデル数化や部分計算可能関数のがある。 (ja) В теорії обчислень нумерація - це присвоєння натуральних номерів множині об'єктів таких як раціональні числа, графи, чи слова в деякій мові. Нумерації можуть використовуватись для передачі поняття обчислюваності і пов'язаних з нею, які формально означені на натуральних числах за допомогою обчислюваних функцій, на ширші класи об'єктів. (uk) 可計算性理論裡，編號（英語：numbering、indexing等）是將一個集合的元素（如函數、有理數、圖、或形式語言的字串）編上自然數號碼。可計算性以及相關的概念最先定義在自然數上，而利用編號，可將這些概念傳遞到上述的其他集合中作討論。 常見例子有一階邏輯的哥德爾編號以及偏可計算函數的。 (zh) Na teoria da computabilidade, numeração é a atribuição de números naturais para um conjunto de objetos como números racionais, gráficos ou palavras em alguma linguagem. A numeração pode ser usada para transferir a idéia de computabilidade e conceitos relacionados, que estão estritamente definidos sobre os números naturais usando funções computáveis, para objetos diferentes. (pt) |
| rdfs:label | Nummerierung (Informatik) (de) Numération (fr) ナンバリング (計算可能性理論) (ja) Numbering (computability theory) (en) Numeração (teoria da computação) (pt) 編號 (可計算性理論) (zh) Нумерація (математика) (uk) |
| owl:sameAs | freebase:Numbering (computability theory) wikidata:Numbering (computability theory) dbpedia-de:Numbering (computability theory) dbpedia-fr:Numbering (computability theory) dbpedia-ja:Numbering (computability theory) dbpedia-pt:Numbering (computability theory) dbpedia-uk:Numbering (computability theory) dbpedia-zh:Numbering (computability theory) https://global.dbpedia.org/id/3LYu7 |
| prov:wasDerivedFrom | wikipedia-en:Numbering_(computability_theory)?oldid=1075402104&ns=0 |
| foaf:isPrimaryTopicOf | wikipedia-en:Numbering_(computability_theory) |
| is dbo:wikiPageRedirects of | dbr:Total_numbering dbr:Comparision_of_numberings dbr:Equivalent_(numbering) dbr:One_equivalent_numbering dbr:Effective_numbering dbr:Reducibility_(numbering) |
| is dbo:wikiPageWikiLink of | dbr:Myhill_isomorphism_theorem dbr:Total_numbering dbr:Cylindric_numbering dbr:Cylindrification dbr:Numbering_scheme dbr:Blum_axioms dbr:Choice_sequence dbr:Complete_numbering dbr:Computable_isomorphism dbr:Friedberg_numbering dbr:Admissible_numbering dbr:Comparision_of_numberings dbr:Equivalent_(numbering) dbr:One_equivalent_numbering dbr:Effective_numbering dbr:Reducibility_(numbering) |
| is foaf:primaryTopic of | wikipedia-en:Numbering_(computability_theory) |