<abstract xmlns="http://www.w3.org/1999/xhtml"> Let En ={xi = 1; xi + xj = xk; xi ∙ xj = xk : i; j; k ∊ {1;. . . ; n}}. We present two algorithms. The first accepts as input any computable function f : ℕ → ℕ and returns a positive integer m( f ) and a computable function g which to each integer n ≥ m( f ) assigns a system S ⊆ En such that S is satisfiable over integers and each integer tuple (x1;. . .; xn) that solves S satisfies x1 = f (n). The second accepts as input any computable function f: ℕ → ℕ and returns a positive integer w( f ) and a computable function h which to each integer n ≥ w( f ) assigns a system S ⊆ En such that S is satisfiable over non-negative integers and each tuple (x1;. . .; xn) of non-negative integers that solves S satisfies x1 = f (n). </abstract>

Let En ={xi = 1; xi + xj = xk; xi ∙ xj = xk : i; j; k ∊ {1;. . . ; n}}. We present two algorithms. The first accepts as input any computable function f : ℕ → ℕ and returns a positive integer m( f ) and a computable function g which to each integer n ≥ m( f ) assigns a system S ⊆ En such that S is satisfiable over integers and each integer tuple (x1;. . .; xn) that solves S satisfies x1 = f (n). The second accepts as input any computable function f: ℕ → ℕ and returns a positive integer w( f ) and a computable function h which to each integer n ≥ w( f ) assigns a system S ⊆ En such that S is satisfiable over non-negative integers and each tuple (x1;. . .; xn) of non-negative integers that solves S satisfies x1 = f (n).

A new characterization of computable functions

University of Agriculture Faculty of Production and Power Engineering Balicka 116B, 30-149 Krakow, Poland

Analele ştiinţifice ale Universităţii "Ovidius" Constanţa. Seria Matematică

{"article-title":"A new characterization of computable functions"}

Let En ={xi = 1; xi + xj = xk; xi ∙ xj = xk : i; j; k ∊ {1;. . . ; n}}. We present two algorithms. The first accepts as input any computable function f : ℕ → ℕ...

A new characterization of computable functions

Publicado en línea: 05 mar 2014

Páginas: 289 - 294

DOI: https://doi.org/10.2478/auom-2013-0059

Palabras clave
computable function, Davis-Putnam-Robinson-Matiyasevich theorem

This content is open access.

A new characterization of computable functions

Publicado en línea: 05 mar 2014

Páginas: 289 - 294

DOI: https://doi.org/10.2478/auom-2013-0059

Palabras clavecomputable function, Davis-Putnam-Robinson-Matiyasevich theorem

This content is open access.

Palabras clave
computable function, Davis-Putnam-Robinson-Matiyasevich theorem