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