Abstract Fried and Kollár constructed a fully faithful functor from the category of graphs to the category of fields. We give a new construction of such a functor and use it to resolve a longstanding open problem in computable model theory, by showing that for every nontrivial countable structure ${\cal S}$ , there exists a countable field ${\cal F}$ of arbitrary characteristic with the same essential computable-model-theoretic properties as ${\cal S}$ . Along the way, we develop a new “computable category theory”, and prove that our functor and its partially defined inverse (restricted to the categories of countable graphs and countable fields) are computable functors.

Abstract We discuss the connection between decidability of a theory of a large algebraic extensions of ${\Bbb Q}$ and the recursiveness of the field as a subset of a fixed algebraic closure. In particular, we prove that if an algebraic extension K of ${\Bbb Q}$ has a decidable existential theory, then within any fixed algebraic closure $\widetilde{\Bbb Q}$ of ${\Bbb Q}$ , the field K must be conjugate over ${\Bbb Q}$ to a field which is recursive as a subset of the algebraic closure. We also show that for each positive integer e there are infinitely many e-tuples $\sigma \in {\text{Gal}}\left( {\Bbb Q} \right)^e $ such that the field $\widetilde{\Bbb Q}\left( \sigma \right)$ is primitive recursive in $\widetilde{\Bbb Q}$ and its elementary theory is primitive recursively decidable. Moreover, $\widetilde{\Bbb Q}\left( \sigma \right)$ is PAC and ${\text{Gal}}\left( {\widetilde{\Bbb Q}\left( \sigma \right)} \right)$ is isomorphic to the free profinite group on e generators.

Abstract We show that a solution to Hilbert's Tenth Problem in the rings of algebraic integers and bigger subrings of number fields where it is currently not known, is equivalent to a problem of bounding archimedean valuations over non-real number fields.

Abstract LetKbe a function field of one variable over a constant fieldCof finite transcendence degree over ℂ. LetM/Kbe a finite extension and letWbe a set of primes ofKsuch that all but finitely many primes ofWdo not split in the extensionM/K. Then there exists a setW′ofK-primes such that Hilbert's Tenth Problem is not decidable overOK,W′= {xϵK∣ordþx≥ 0, ∀þ ∉W′}, and the set (W′ ∖W)∪{W∖W′) is finite. LetKbe a function field of one variable over a constant fieldCfinitely generated over ℚ. LetM/Kbe a finite extension and letWbe a set of primes ofKsuch that all but finitely many primes ofWdo not split in the extensionM/Kand the degree of all the primes inWis bounded bybϵ ℕ. Then there exists a setW′ ofK-primes such that ℤ has a Diophantine definition overOK,W′, and the set (W′ ∖W)∪(W∖W′) is finite.

Abstract Let K be a computable field. Let ℱ be a collection of recursive functions over K, possibly including field operations. We investigate the following question. Given an r.e. degree . is there an injective map j : K → ℕ such that j(K) is of degree a and all the functions in ℱ are translated by restrictions of total recursive functions.

Abstract We show that Diophantine equivalence of two suitably presented countable rings implies that the existential polynomial languages of the two rings have the same “expressive power” and that their Diophantine sets are in some sense the same. We also show that a Diophantine class of countable rings is contained completely within a relative enumeration class and demonstrate that one consequence of this fact is the existence of infinitely many Diophantine classes containing holomorphy rings of ℚ.

Abstract One of the main theorems of the paper states the following. Let R-K-M be finite extensions of a rational one variable function field R over a finite field of constants. Let S be a finite set of valuations of K. Then the ring of elements of K having no poles outside S has a Diophantine definition over its integral closure in M.