A new characterization of computable functions

Apoloniusz Tyszka

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).
Author Apoloniusz Tyszka (FoPaPE)
Apoloniusz Tyszka,,
- Faculty of Production and Power Engineering
Journal seriesAnalele Stiintifice ale Universitatii Ovidius Constanta-Seria Matematica, ISSN 1224-1784, (A 15 pkt)
Issue year2013
Vol21
No3
Pages289-293
Publication size in sheets0.5
Keywords in Englishcomputable function, Davis-Putnam-Robinson-Matiyasevich theorem
DOIDOI:10.2478/auom-2013-0059
URL http://www.degruyter.com/view/j/auom.2013.21.issue-3/auom-2013-0059/auom-2013-0059.xml
Internal identifierWIPiE/2013/110
Languageen angielski
Score (nominal)15
ScoreMinisterial score = 15.0, 26-07-2017, ArticleFromJournal
Ministerial score (2013-2016) = 15.0, 26-07-2017, ArticleFromJournal
Citation count*1 (2016-03-01)
Cite
Share Share

Get link to the record


* presented citation count is obtained through Internet information analysis and it is close to the number calculated by the Publish or Perish system.
Back
Confirmation
Are you sure?