MuPAD codes which implement limit-computable functions that cannot be bounded by any computable function

• Autorzy: Apoloniusz Tyszka
• Języki publikacji: EN

Abstrakty

EN

Let E_n={x_k=1, x_i+x_j=x_k, x_i · x_j=x_k: 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 ⊆ E_n with a solution in non-negative integers x_1,...,x_n there exists a solution of S in non-negative integers not greater than b. We prove that if a function G:N{0}-->N is computable, then f dominates G i.e. there exists a positive integer m such that G(n)

Słowa kluczowe

EN

Object-oriented programming (OOP); Algorithms; Mathematical analysis

PL

Programowanie obiektowe; Algorytmy; Analiza matematyczna

• Czasopismo: Annals of Computer Science and Information Systems
• Rocznik: 2014
• Tom: 2
• Strony: 623--629

Twórcy

autor

Apoloniusz Tyszka

• University of Agriculture

Bibliografia

• Ebbinghaus H. -D. and Flum J., Finite model theory, Springer-Verlag, Berlin, 2006.
• Janiczak A., Some remarks on partially recursive functions, Colloquium Math. 3 (1954), 37-38.
• Matiyasevich Yu., Hilbert's tenth problem, MIT Press, Cambridge, MA, 1993.
• Matiyasevich Yu., Towards finite-fold Diophantine representations, Zap Nauchn. Sem. S.-Peterburg. Otdel. Mat. Inst. Steklov. (POMI) 377 (2010), 78-90, ftp://ftp.pdmi.ras.ru/pub/publicat/znsl/v377/p078.pdf, http://dx.doi.org/10.1007/s10958-010-0179-4.
• Murawski R., The contribution of Polish logicians to recursion theory, in: K. Kijania-Placek and J. Wole´nski (eds.), The Lvov-Warsaw School and Contemporary Philosophy, 265-282, Kluwer Acad. Publ., Dordrecht, 1998.
• Soare R. I., Interactive computing and relativized computability, in: Computability: Turing, G¨odel, Church, and beyond (eds. B. J. Copeland, C. J. Posy, and O. Shagrir), MIT Press, Cambridge, MA, 2013, 203-260.
• Tyszka A., A condition equivalent to the decidability of Diophantine equations with a finite number of solutions in non-negative integers, http://arxiv.org/abs/1404.5975.
• Tyszka A., Conjecturally computable functions which unconditionally do not have any finite-fold Diophantine representation, Inform. Process. Lett. 113 (2013), no. 19-21, 719-722, http://dx.doi.org/10.1016/j.ipl. 2013.07.004.
• Tyszka A., Does there exist an algorithm which to each Diophantine equation assigns an integer which is greater than the modulus of integer solutions, if these solutions form a finite set? Fund. Inform. 125(1): 95-99, 2013, http://dx.doi.org/10.3233/FI-2013-854.
• Tyszka A., Four MuPAD codes, http://www.cyf-kr.edu.pl/∼rttyszka/codes.txt.
• Tyszka A., Links to an installation file for MuPAD Light, http://www.ts.mah.se/utbild/ma7005/mupad light scilab 253.exe, http://caronte.dma.unive.it/info/materiale/mupad light scilab 253.exe, http://www.cyf-kr.edu.pl/∼rttyszka/mupad light scilab 253.exe, http://www.cyf-kr.edu.pl/∼rttyszka/mupad light 253.exe, http://www. projetos.unijui.edu.br/matematica/amem/mupad/mupad light 253.exe.