A new characterization of computable functions

Details A new characterization of computable functions A new characterization of computable functions

2010-11-17

arxiv.org/abs/1011.4103v28

Mathematics

Logic

6 pages, Theorem 2 added. arXiv admin note: substantial text overlap with arXiv:1102.4122, arXiv:0901.2093, arXiv:1105.5747

Scientific paper

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

Affiliated with

Also associated with

No associations

Rating

A new characterization of computable functions does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with A new characterization of computable functions, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A new characterization of computable functions will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-535993