All Functions g: ℕ → ℕ $$g: \mathbb{N} \rightarrow \mathbb{N}$$ Which have a Single-Fold Diophantine Representation are Dominated by a Limit-Computable Function f: ℕ ∖ { 0 } → ℕ $$f: \mathbb{N}\setminus \{0\} \rightarrow \mathbb{N}$$ Which is Implemented in MuPAD and Whose Computability is an Open Problem

Apoloniusz Tyszka ()
Additional contact information
Apoloniusz Tyszka: University of Agriculture, Faculty of Production and Power Engineering

A chapter in Computation, Cryptography, and Network Security, 2015, pp 577-590 from Springer

Abstract: Abstract Let g : ℕ → ℕ $$E_{n} =\{ x_{k} = 1,\ x_{i} + x_{j} = x_{k},\ x_{i} \cdot x_{j} = x_{k}: i,j,k \in \{ 1,\ldots,n\}\}$$ . For any integer n ≥ 2214, we define a system f : ℕ ∖ { 0 } → ℕ $$T \subseteq E_{n}$$ which has a unique integer solution (a 1, …, a n ). We prove that the numbers a 1, …, a n are positive and max a 1 , … , a n > 2 2 n $$\mathrm{max}\left (a_{1},\ldots,a_{n}\right ) > 2^{2^{n} }$$ . For a positive integer n, let f(n) denote the smallest non-negative integer b such that for each system S ⊆ E n $$S \subseteq E_{n}$$ with a unique solution in non-negative integers x 1, …, x n , this solution belongs to [0, b] n . We prove that if a function g : ℕ → ℕ $$g: \mathbb{N} \rightarrow \mathbb{N}$$ has a single-fold Diophantine representation, then f dominates g. We present a MuPAD code which takes as input a positive integer n, performs an infinite loop, returns a non-negative integer on each iteration, and returns f(n) on each sufficiently high iteration.

Keywords: Davis-Putnam-Robinson-Matiyasevich theorem; Diophantine equation with a unique integer solution; Diophantine equation with a unique solution in non-negative integers; Limit-computable function; Single-fold Diophantine representation; Trial-and-error computable function (search for similar items in EconPapers)
Date: 2015
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:sprchp:978-3-319-18275-9_24

Ordering information: This item can be ordered from
http://www.springer.com/9783319182759

DOI: 10.1007/978-3-319-18275-9_24

Access Statistics for this chapter

More chapters in Springer Books from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().