Have a personal or library account? Click to login
A new characterization of computable functions Cover

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).

DOI: https://doi.org/10.2478/auom-2013-0059 | Journal eISSN: 1844-0835 | Journal ISSN: 1224-1784
Language: English
Page range: 289 - 294
Published on: Mar 5, 2014
Published by: Ovidius University of Constanta
In partnership with: Paradigm Publishing Services
Publication frequency: 3 issues per year

© 2014 Apoloniusz Tyszka, published by Ovidius University of Constanta
This work is licensed under the Creative Commons License.