On Hypercomputation, Universal and Diagonalization Complete Problems

• Autorzy: Eberbach E.

Identyfikatory

DOI

10.3233/FI-2015-1237

• Języki publikacji: EN

Abstrakty

EN

In the paper we define the class of hypercomputation complete and hard undecidable problems. We prove that typical unsolvable problems are decidable in infinity. We hypothesize that all undecidable problems can be reduced in infinity to each other, i.e., they are H-complete (hypercomputation complete). We propose also two other classes: U-complete (universal complete) and D-complete (diagonalization complete) that use asymptotic reduction and allow separate non- RE and RE non-recursive undecidable classes.

Słowa kluczowe

EN

problem solving; hypercomputation; S-calculus; undecidability; p-decidability; e-decidability; a-decidability; i-decidability; H-completeness; U-completeness; D-completeness

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2015
• Tom: Vol. 139, nr 4
• Strony: 329--346
• Opis fizyczny: Bibliogr. 32 poz.

Twórcy

autor

Eberbach E.

• Department of Engineering and Science Rensselaer Polytechnic Institute 275 Windsor Street, Hartford, CT 06120, USA

Bibliografia

• [1] Aho, A., Computation and Computational Thinking, Ubiquity ACM symposiumWhat is computation, Ubiquity Magazine, Vol.2011, Issue January, Article no.1, Jan. 2011, doi: 10.1145/1922681.1922682.
• [2] Bringsjord S., Eberbach E., G. Naveen S., Yang Y., Might the Rigorous Modeling of Economic Phenomena Require Hypercomputation?, Proc. of HyperNet 10: The UC2010 HypercomputationWorkshop, Unconventional Computation 2010 Conference, Tokyo, 2010,15-29.
• [3] Bringsjord S., G. Naveen S., Eberbach E., Yang Y., Perhaps the RigorousModeling of Economic Phenomena Requires Hypercomputation, Int. Journal of Unconventional Computing, vol.8, no.1, 2012, 3-32.
• [4] Burgin M., Super-Recursive Algorithms, Springer-Verlag, 2005.
• [5] Burgin M., Eberbach E., Evolutionary Automata: Expressiveness and Convergence of Evolutionary Computation, Computer Journal, 55(9), 2012, 1023-1029, doi: dx.doi.org/10.1093/comjnl/bxr099.
• [6] Church A., An Unsolvable Problem of Elementary Number Theory, American Journal of Mathematics, vol.58, 1936, 345-363.
• [7] Cooper B., Turings Titanic Machine?, CACM, vol.55, no.3, March 2012, 74-83, doi:10.1145/2093548.2093569.
• [8] Denning, P., What Have We Said About Computation? Closing Statement, Ubiquity ACM symposium What is computation, Ubiquity Magazine, Vol.2011, Issue April, Article no.1, April 2011, doi:10.1145/1967045.1967046.
• [9] Eberbach E., A Generic Tool for Distributed AI with Matching as Message Passing, Proc. of the Ninth IEEE Intern. Conf. on Tools with Artificial Intelligence TAI’97, Newport Beach, California, 1997, 11-18.
• [10] Eberbach E., Is EntscheidungsproblemSolvable? Beyond Undecidability of Turing Machines and Its Consequence for Computer Science and Mathematics, in: (ed.J.C.Misra) Computational Mathematics, Modelling and Algorithms, Narosa Publishing House, New Delhi, 2003, 1-32.
• [11] Eberbach E.,Wegner P., Beyond Turing Machines, The Bulletin of the European Association for Theoretical Computer Science (EATCS Bulletin), 81, Oct. 2003, 279-304.
• [12] Eberbach E., Goldin D., Wegner P., Turing’s Ideas and Models of Computation, in: (ed. Ch.Teuscher) Alan Turing: Life and Legacy of a Great Thinker, Springer-Verlag, 2004, 159-194.
• [13] Eberbach E., $-Calculus of Bounded Rational Agents: Flexible Optimization as Search under Bounded Resources in Interactive Systems, Fundamenta Informaticae, vol.68, no.1-2, 2005, 47-102.
• [14] Eberbach E., Toward a Theory of Evolutionary Computation, BioSystems, vol.82, no.1, 2005, 1-19.
• [15] Eberbach E., Expressiveness of the _-Calculus and the $-Calculus, Proc. 2006World Congress in Comp. Sci., Comp. Eng., & Applied Computing, The 2006 Intern. Conf. on Foundations of Computer Science FCS’06, Las Vegas, Nevada, 2006, 24-30.
• [16] Eberbach E., The $-Calculus Process Algebra for Problem Solving: A Paradigmatic Shift in Handling Hard Computational Problems, Theoretical Computer Science, vol.383, no.2-3, 2007, 200-243 (doi:dx.doi.org/10.1016/j.tcs.2007.04.012).
• [17] Gasarch B., Hemaspaandra L.A., SIGACT News Complexity Theory Column 36, vol.33, issue 2, June 2002, pp.34-47.
• [18] Gödel K., Űber formal unentscheidbare S¨atze der Principia Mathematica und verwander Systeme, Monatschefte f¨ur Mathematik und Physik, 38:173-198, 1931.
• [19] Hopcroft J.E., Motwani R., Ullman J.D., Introduction to Automata Theory, Languages, and Computation, 3rd ed., Addison-Wesley, 2007.
• [20] Horvitz E., Zilberstein S. (eds.), Computational Tradeoffs under Bounded Resources, Artificial Intelligence 126, 2001, 1-196.
• [21] Kozen D.C., Automata and Computability, Springer-Verlag, 1997.
• [22] Milner R., Parrow J., Walker D., A Calculus of Mobile Processes, Rep. ECS-LFCS-89-85 and -86, Lab. For Foundations of Computer Science, Computer Science Dept., Edinburgh Univ., 1989.
• [23] Milner R., Communicating and Mobile Systems: The _-calculus, Cambridge University Press, 1999.
• [24] Post E., A Variant of a Recursively Unsolvable Problem, Bulletin of the AMS 52, 1946, 264-268.
• [25] Rado T., On Non-Computable Functions, Bell System Technical Journal, vol.41, no.3, 1962, 877-884.
• [26] Rice H.G., Classes of Recursively Enumerable Sets and their Decision Problems, Trans. of the AMS 89, 1953, 25-59.
• [27] Russell S., Norvig P., Artificial Intelligence: A Modern Approach, Prentice-Hall, 3rd ed., 2010.
• [28] Syropoulos A., Hypercomputation: Computing Beyond the Church-Turing Barrier, Springer-Verlag, 2008.
• [29] Turing A., On Computable Numbers, with an Application to the Entscheidungsproblem, Proc. LondonMath. Soc., 42-2, 1936, 230-265; A correction, ibid, 43, 1937, 544-546.
• [30] Turing A., Systems of Logic based on Ordinals, Proc. London Math. Soc. Series 2, 45, 1939, 161-228.
• [31] Wegner P., Eberbach E., Burgin M., Computational Completeness of Interaction Machines and Turing Machines, Proc. The Turing Centenary Conference, Turing-100, Alan Turing Centenary, EasyChair Proc. in Computing, EPiC vol. 10 (ed. A. Voronkov),Manchester, UK, June 2012,405-414.
• [32] Whitehead A.N., Russell B., Principia Mathematica, vol.1, 1910, vol.2, 1912, vol.3, 1913, Cambridge Univ. Press, London.