A new characterization of computable functions

MaRDI QIDQ2922764zbMATH OpenFDO

Authors Apoloniusz Tyszka

Publication date 14 October 2014

Published in Analele Științifice ale Universității ``Ovidius Constanța. Seria: Matematică (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1011.4103

zbMATH Keywords

computable functionDavis-Putnam-Robinson-Matiyasevich theorem

Mathematics Subject Classification ID

Recursive functions and relations, subrecursive hierarchies (03D20) Model theory (number-theoretic aspects) (11U09)

Abstract: Let E_n={x_i=1, x_i+x_j=x_k, x_i*x_j=x_k: i,j,k in {1,...,n}}. We prove: (1) there is an algorithm that for every computable function f:N-->N returns a positive integer m(f), for which a second algorithm accepts on the input f and any integer n>=m(f), and returns a system S subseteq E_n such that S is consistent over the integers and each integer tuple (x_1,...,x_n) that solves S satisfies x_1=f(n), (2) there is an algorithm that for every computable function f:N-->N returns a positive integer w(f), for which a second algorithm accepts on the input f and any integer n>=w(f), and returns a system S subseteq E_n such that S is consistent over N and each tuple (x_1,...,x_n) of non-negative integers that solves S satisfies x_1=f(n).

Recommendations

• Conjecturally computable functions which unconditionally do not have any finite-fold Diophantine representation
• All Functions $$g: \mathbb{N} \rightarrow \mathbb{N}$$ Which have a Single-Fold Diophantine Representation are Dominated by a Limit-Computable Function $$f: \mathbb{N}\setminus \{0\} \rightarrow \mathbb{N}$$ Which is Implemented in MuPAD and Whose Computa
• Introduction to computability
• A characterization of computable analysis on unbounded domains using differential equations
• Characterizing Computable Analysis with Differential Equations

Cited in

(10)

• A term rewriting characterization of the functions computable in polynomial space
• The Veblen functions for computability theorists
• Classes of computable functions defined by bounds on computation
• scientific article; zbMATH DE number 7360045 (Why is no real title available?)
• Computability and the Implicit Function Theorem
• Functions computable with limited access to NP
• Beyond Rogers’ Non-constructively Computable Function
• Iterative Characterizations of Computable Unary Functions: A General Method
• scientific article; zbMATH DE number 4033742 (Why is no real title available?)
• Some characterizations of functions computable in on-line arithmetic

This page was built for publication: A new characterization of computable functions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2922764)