Non-coding Enumeration Operators
| Autor: | Russell Miller |
|---|---|
| Rok vydání: | 2020 |
| Předmět: |
Meagre set
Turing degree Lebesgue measure 010102 general mathematics Prime number Natural number 0102 computer and information sciences 01 natural sciences Combinatorics symbols.namesake 010201 computation theory & mathematics Enumeration symbols Hilbert's tenth problem 0101 mathematics Algebraic number Mathematics |
| Zdroj: | Lecture Notes in Computer Science ISBN: 9783030514655 CiE |
| DOI: | 10.1007/978-3-030-51466-2_10 |
| Popis: | An enumeration operator maps each set A of natural numbers to a set \(E(A)\subseteq \mathbb {N}\), in such a way that E(A) can be enumerated uniformly from every enumeration of A. The maximum possible Turing degree of E(A) is therefore the degree of the jump \(A'\). It is impossible to have \(E(A)\equiv _T A'\) for all A, but possible to achieve this for all A outside a meager set of Lebesgue measure 0. We consider the properties of two specific enumeration operators: the HTP operator, mapping a set W of prime numbers to the set of polynomials realizing Hilbert’s Tenth Problem in the ring \(\mathbb {Z}[W^{-1}]\); and the root operator, mapping the atomic diagram of an algebraic field F of characteristic 0 to the set of polynomials in \(\mathbb {Z}[X]\) with roots in F. These lead to new open questions about enumeration operators in general. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|