Mathematics – Logic
Scientific paper
2011-07-28
Mathematics
Logic
10 pages, Theorem 3 added
Scientific paper
For K \subseteq C, let B_n(K)={(x_1,...,x_n) \in K^n: for each y_1,...,y_n \in K the conjunction (\forall i \in {1,...,n} (x_i=1 => y_i=1)) AND (\forall i,j,k \in {1,...,n} (x_i+x_j=x_k => y_i+y_j=y_k)) AND (\forall i,j,k \in {1,...,n} (x_i*x_j=x_k => y_i*y_j=y_k)) implies that x_1=y_1}. We claim that 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 tuple (x_1,...,x_n) \in B_n(Z) with x_1=f(n). We compute an integer tuple (x_1,...,x_{20}) for which the statement (x_1,...,x_{20}) \in B_{20}(Z) is equivalent to an open Diophantine problem. We prove that if the set B_n(Z) (B_n(N), B_n(N \setminus {0})) is not computable for some n, then there exists a Diophantine equation whose solvability in integers (non-negative integers, positive integers) is logically undecidable.
No associations
LandOfFree
A subset of Z^n whose non-computability leads to the existence of a Diophantine equation whose solvability is logically undecidable 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 subset of Z^n whose non-computability leads to the existence of a Diophantine equation whose solvability is logically undecidable, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A subset of Z^n whose non-computability leads to the existence of a Diophantine equation whose solvability is logically undecidable will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-413285