DocumentCode :
130392
Title :
MuPAD codes which implement limit-computable functions that cannot be bounded by any computable function
Author :
Tyszka, Apoloniusz
Author_Institution :
Fac. of Production & Power Eng., Univ. of Agric., Kraków, Poland
fYear :
2014
fDate :
7-10 Sept. 2014
Firstpage :
623
Lastpage :
629
Abstract :
Let En = {xk = 1, xi + xj = xk, xi · xj = xk : i, j, k ∈ {1, ..., n}}. For a positive integer n, let f (n) denote the smallest non-negative integer b such that for each system S ⊆ En with a solution in non-negative integers x1, ..., xn there exists a solution of S in non-negative integers not greater than b. We prove that if a function Γ : ℕ {0} → ℕ is computable, then f dominates Γ i.e. there exists a positive integer m such that Γ(n) <; f (n) for any n ≥ m. For positive integers n, m, let g(n,m) denote the smallest non-negative integer b such that for each system S ⊆ En with a solution in {0, ..., m - 1}n there exists a solution of S in {0, ..., b}n. Then, equations and equation We present an infinite loop in MuPAD which takes as input a positive integer n and returns g(n,m) on the m-th iteration.
Keywords :
Turing machines; computability; set theory; MuPAD codes; Turing computation; computable function; infinite loop; limit-computable functions; nonnegative integers; positive integers; Computational modeling; Computer science; Computers; Information systems; Mathematical model; Polynomials; Hilbert´s Tenth Problem; MuPAD; infinite loop; limit-computable function; trial-and-error computable function;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Computer Science and Information Systems (FedCSIS), 2014 Federated Conference on
Conference_Location :
Warsaw
Type :
conf
DOI :
10.15439/2014F91
Filename :
6933072
Link To Document :
بازگشت