On Completeness of Cost Metrics and Meta-Search Algorithms in $-Calculus

Eberbach, Eugene

Artykuł - szczegóły

Tytuł artykułu

On Completeness of Cost Metrics and Meta-Search Algorithms in $-Calculus

Autorzy

Eberbach Eugene

Wybrane pełne teksty z tego czasopisma

https://fi.episciences.org/

Identyfikatory

URI

10.3233/FI-222142

Warianty tytułu

Języki publikacji

Abstrakty

In the paper we define three new complexity classes for Turing Machine undecidable problems inspired by the famous Cook/Levin's NP-complete complexity class for intractable problems. These are U-complete (Universal complete), D-complete (Diagonalization complete) and H-complete (Hypercomputation complete) classes. In the paper, in the spirit of Cook/Levin/Karp, we started the population process of these new classes assigning several undecidable problems to them. We justify that some super-Turing models of computation, i.e., models going beyond Turing machines, are tremendously expressive and they allow to accept arbitrary languages over a given alphabet including those undecidable ones. We prove also that one of such super-Turing models of computation - the $-Calculus, designed as a tool for automatic problem solving and automatic programming, has also such tremendous expressiveness. We investigate also completeness of cost metrics and meta-search algorithms in $-calculus.

Słowa kluczowe

automatic problem solving automatic programming undecidability intractablity recursive algorithms recursively enumerable but not recursive algorithms non-recursively enumerable algorithms super-Turing computation super-recursive algorithms p-decidability e-decidability a-decidability i-decidability reduction techniques U-completeness D-completeness H-completeness $-calculus cost metrics completeness meta-search algorithms completeness

Wydawca

IOS Press

Czasopismo

Fundamenta Informaticae

Rocznik

2022

Tom

Vol. 188 nr 2

Strony

63--90

Opis fizyczny

Bibliogr. 42 poz., rys.

Twórcy

autor

Eberbach Eugene

eeberbach@gmail.com

Department of Engineering and Science Rensselaer Polytechnic Institute, Hartford, CT, USA

Bibliografia

[1] Aho A. Computation and Computational Thinking, Ubiquity ACM symposium “What is computation”, Ubiquity Magazine, Vol.2011, Issue January, Article no.1, Jan. 2011, doi:10.1145/1922681.1922682.
[2] Ansari B. $-cala: An Embedded Programming Language Based on $-Calculus and Scala, Master Thesis, Rensselaer Polytechnic Institute at Hartford, Dept. of Eng. and Science, 2013.
[3] Bringsjord SG, Naveen S, Eberbach E, Yang Y. Perhaps the Rigorous Modeling 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. doi:10.1007/b138114.
[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] Buzzell Ch. A Common Control Language for Multiple Autonomous Undersea Vehicle Cooperation, Master Thesis, Univ. of Massachusetts Dartmouth, Intercampus Graduate School of Marine Sciences and Technology, 2005.
[7] Church A. An Unsolvable Problem of Elementary Number Theory, American Journal of Mathematics, vol.58, 1936, 345-363. URL http://links.jstor.org/sici?sici=0002-9327%28193604%2958% 3A2%3C345%3AAUPOEN%3E2.0.CO%3B2-1
[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] Duarte Ch, Martel G, E[1] Aho A. Computation and Computational Thinking, Ubiquity ACM symposium “What is computation”, Ubiquity Magazine, Vol.2011, Issue January, Article no.1, Jan. 2011, doi:10.1145/1922681.1922682.
[2] Ansari B. $-cala: An Embedded Programming Language Based on $-Calculus and Scala, Master Thesis, Rensselaer Polytechnic Institute at Hartford, Dept. of Eng. and Science, 2013.
[3] Bringsjord SG, Naveen S, Eberbach E, Yang Y. Perhaps the Rigorous Modeling 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. doi:10.1007/b138114.
[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] Buzzell Ch. A Common Control Language for Multiple Autonomous Undersea Vehicle Cooperation, Master Thesis, Univ. of Massachusetts Dartmouth, Intercampus Graduate School of Marine Sciences and Technology, 2005.
[7] Church A. An Unsolvable Problem of Elementary Number Theory, American Journal of Mathematics, vol.58, 1936, 345-363. URL http://links.jstor.org/sici?sici=0002-9327%28193604%2958% 3A2%3C345%3AAUPOEN%3E2.0.CO%3B2-1
[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] Duarte Ch, Martel G, Eberbach E, Buzzell Ch. A Common Control Language for Dynamic Tasking of Multiple Autonomous Vehicles, Proc. of the 13th Intern. Symp. on Unmanned Untethered Submersible Technology UUST’03, Durham, NH, August 24-27, 2003.
[10] Eberbach E. SEMAL: A Cost Language Based on the Calculus of Self-modifiable Algorithms, Intern. Journal of Software Engineering and Knowledge Engineering, vol.4, no.3, 1994, 391-408. doi:10.1142/S0218194094000192.
[11] Eberbach E, Phoha S. SAMON: Communication, Cooperation and Learning of Mobile Autonomous Robotic Agents, Proc. of the 11th IEEE Intern. Conf. on Tools with Artificial Intelligence ICTAI’99, Chicago, IL, 1999, 229-236. doi:10.1109/TAI.1999.809791.
[12] Eberbach E, Wegner P. Beyond Turing Machines, The Bulletin of the European Association for Theoretical Computer Science (EATCS Bulletin), 81, Oct. 2003, 279-304.
[13] 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. doi:10.1007/978-3-662-05642-4 7.
[14] Eberbach E, Eberbach A. On Designing CO$T: A New Approach and Programming Environment for Distributed Problem Solving Based on Evolutionary Computation and Anytime Algorithms, Proc. 2004 Congress on Evolutionary Computation CEC’2004, vol.2, Portland, Oregon, 2004, 1836-1843.
[15] 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.
[16] Eberbach E. Toward a Theory of Evolutionary Computation, BioSystems, vol.82, no.1, 2005, 1-19. doi:10.1016/j.biosystems.2005.05.006.
[17] 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:10.1016/j.tcs.2007.04.012.
[18] Eberbach E. Approximate Reasoning in the Algebra of Bounded Rational Agents, Intern. Journal of Approximate Reasoning, vol.49, issue 2, 2008, 316-330 doi:10.1016/j.ijar.2006.09.014.
[19] Eberbach E. On Hypercomputation, Universal and Diagonalization Complete Problems, Fundamenta Informaticae, IOS Press, 139 (4), 2015, 329-346, doi:10.3233/FI-2015-1237.
[20] Eberbach E, Strzalka D. In Search of Machine Learning Theory, Proc. Future Technologies Conference FTC’2021, Springer, Lect. Notes in Networks and Systems, Oct. 28-29, 2021, Vancouver, BC, https://saiconference.com/FTC2021.
[21] Eberbach E. Undecidability and Complexity for Super-Turing Models of Computation, Proc. Conf. on Theoretical and Foundational Problems in Information Studies, IS4SI 2021, The 2021 Summit of the Intern. Society for the Study of Information, Sept. 12-19, 2021, Proceedings 2022, 81, 123, doi:10.3990/proceedings2022081123.
[22] G¨odel K. ¨Uber formal unentscheidbare S¨atze der Principia Mathematica und verwander Systeme, Monatschefte fur Mathematik und Physik, 38:173-198, 1931.
[23] Hopcroft JE, Motwani R, Ullman JD. Introduction to Automata Theory, Languages, and Computation, 3rd ed., Addison-Wesley, 2007. ISBN-13:9780321455369.
[24] Horree S. Design and Implementation of a Version of SEMAL Interpreter, Honors Thesis, Jodrey School of Computer Science, Acadia University, 1994.
[25] Horvitz E. Zilberstein S. (eds.), Computational Tradeoffs under Bounded Resources, Artificial Intelligence 126, 2001, 1-196.
[26] Kleinberg J, Tardos E. Algorithm Design, Pearson/Addison Wesley, 2006. ISBN-13:9780137546350.
[27] Kozen DC. Automata and Computability, Springer-Verlag, 1997.
[28] Kuratowki K. Introduction to Set Theory and Topology, PWN, Warsaw, 1977.
[29] 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.
[30] Milner R. Communicating and Mobile Systems: The π-calculus, Cambridge University Press, 1999. ISBN:9780521658690.
[31] Pesonen V. New Models of Computation, 2011, https://slideplayer.com/slide/11412947/.
[32] Post E. A Variant of a Recursively Unsolvable Problem, Bulletin of the AMS 52, 1946, 264-268.
[33] Rado T. On Non-Computable Functions, Bell System Technical Journal, vol.41, no.3, 1962, 877-884. doi:10.1002/j.1538-7305.1962.tb00480.x.
[34] Rice HG. Classes of Recursively Enumerable Sets and their Decision Problems, Trans. of the AMS 89, 1953, 25-59. doi:10.1090/S0002-9947-1953-0053041-6.
[35] Russell S, Norvig P. Artificial Intelligence: A Modern Approach, Prentice-Hall, 3rd ed., 2010. ISBN-10:0136042597, 13:978-0136042594.
[36] Smith J. $-Calcu Lisp, an Implementation of $-Calculus Process Algebra in Common Lisp, Master Project, Rensselaer Polytechnic Institute at Hartford, Dept. of Eng. and Science, 2013.
[37] Syropoulos A. Hypercomputation: Computing Beyond the Church-Turing Barrier, Springer-Verlag, 2008. doi:10.1007/978-0-387-49970-3.
[38] Turing A. On Computable Numbers, with an Application to the Entscheidungs problem, Proc. London Math. Soc., 42-2, 1936, 230-265; A correction, ibid, 43, 1937, 544-546. doi:10.1112/plms/s2-42.1.230.
[39] Turing A. Systems of Logic based on Ordinals, Proc. London Math. Soc. Series 2, 45, 1939, 161-228. doi:10.1112/plms/s2-45.1.161.
[40] Turing, A. Intelligent Machinery, 1948, in Collected Works of A.M. Turing: Mechanical Intelligence, ed.D.C.Ince, Elsevier Science, 1992.
[41] 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.
[42] Whitehead AN, Russell B. Principia Mathematica, vol.1, 1910, ISBN-10:1603861823, 13:978-1603861823. vol.2, 1912, https://www.slideshare.net/Kadio3/insurance-250661884, vol.3, 1913, Cambridge Univ. Press, London.
berbach E, Buzzell Ch. A Common Control Language for Dynamic Tasking of Multiple Autonomous Vehicles, Proc. of the 13th Intern. Symp. on Unmanned Untethered Submersible Technology UUST’03, Durham, NH, August 24-27, 2003.
[10] Eberbach E. SEMAL: A Cost Language Based on the Calculus of Self-modifiable Algorithms, Intern. Journal of Software Engineering and Knowledge Engineering, vol.4, no.3, 1994, 391-408. doi:10.1142/S0218194094000192.
[11] Eberbach E, Phoha S. SAMON: Communication, Cooperation and Learning of Mobile Autonomous Robotic Agents, Proc. of the 11th IEEE Intern. Conf. on Tools with Artificial Intelligence ICTAI’99, Chicago, IL, 1999, 229-236. doi:10.1109/TAI.1999.809791.
[12] Eberbach E, Wegner P. Beyond Turing Machines, The Bulletin of the European Association for Theoretical Computer Science (EATCS Bulletin), 81, Oct. 2003, 279-304.
[13] 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. doi:10.1007/978-3-662-05642-4 7.
[14] Eberbach E, Eberbach A. On Designing CO$T: A New Approach and Programming Environment for Distributed Problem Solving Based on Evolutionary Computation and Anytime Algorithms, Proc. 2004 Congress on Evolutionary Computation CEC’2004, vol.2, Portland, Oregon, 2004, 1836-1843.
[15] 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.
[16] Eberbach E. Toward a Theory of Evolutionary Computation, BioSystems, vol.82, no.1, 2005, 1-19. doi:10.1016/j.biosystems.2005.05.006.
[17] 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:10.1016/j.tcs.2007.04.012.
[18] Eberbach E. Approximate Reasoning in the Algebra of Bounded Rational Agents, Intern. Journal of Approximate Reasoning, vol.49, issue 2, 2008, 316-330 doi:10.1016/j.ijar.2006.09.014.
[19] Eberbach E. On Hypercomputation, Universal and Diagonalization Complete Problems, Fundamenta Informaticae, IOS Press, 139 (4), 2015, 329-346, doi:10.3233/FI-2015-1237.
[20] Eberbach E, Strzalka D. In Search of Machine Learning Theory, Proc. Future Technologies Conference FTC’2021, Springer, Lect. Notes in Networks and Systems, Oct. 28-29, 2021, Vancouver, BC, https://saiconference.com/FTC2021.
[21] Eberbach E. Undecidability and Complexity for Super-Turing Models of Computation, Proc. Conf. on Theoretical and Foundational Problems in Information Studies, IS4SI 2021, The 2021 Summit of the Intern. Society for the Study of Information, Sept. 12-19, 2021, Proceedings 2022, 81, 123, doi:10.3990/proceedings2022081123.
[22] G¨odel K. ¨Uber formal unentscheidbare S¨atze der Principia Mathematica und verwander Systeme, Monatschefte fur Mathematik und Physik, 38:173-198, 1931.
[23] Hopcroft JE, Motwani R, Ullman JD. Introduction to Automata Theory, Languages, and Computation, 3rd ed., Addison-Wesley, 2007. ISBN-13:9780321455369.
[24] Horree S. Design and Implementation of a Version of SEMAL Interpreter, Honors Thesis, Jodrey School of Computer Science, Acadia University, 1994.
[25] Horvitz E. Zilberstein S. (eds.), Computational Tradeoffs under Bounded Resources, Artificial Intelligence 126, 2001, 1-196.
[26] Kleinberg J, Tardos E. Algorithm Design, Pearson/Addison Wesley, 2006. ISBN-13:9780137546350.
[27] Kozen DC. Automata and Computability, Springer-Verlag, 1997.
[28] Kuratowki K. Introduction to Set Theory and Topology, PWN, Warsaw, 1977.
[29] 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.
[30] Milner R. Communicating and Mobile Systems: The π-calculus, Cambridge University Press, 1999. ISBN:9780521658690.
[31] Pesonen V. New Models of Computation, 2011, https://slideplayer.com/slide/11412947/.
[32] Post E. A Variant of a Recursively Unsolvable Problem, Bulletin of the AMS 52, 1946, 264-268.
[33] Rado T. On Non-Computable Functions, Bell System Technical Journal, vol.41, no.3, 1962, 877-884. doi:10.1002/j.1538-7305.1962.tb00480.x.
[34] Rice HG. Classes of Recursively Enumerable Sets and their Decision Problems, Trans. of the AMS 89, 1953, 25-59. doi:10.1090/S0002-9947-1953-0053041-6.
[35] Russell S, Norvig P. Artificial Intelligence: A Modern Approach, Prentice-Hall, 3rd ed., 2010. ISBN-10:0136042597, 13:978-0136042594.
[36] Smith J. $-Calcu Lisp, an Implementation of $-Calculus Process Algebra in Common Lisp, Master Project, Rensselaer Polytechnic Institute at Hartford, Dept. of Eng. and Science, 2013.
[37] Syropoulos A. Hypercomputation: Computing Beyond the Church-Turing Barrier, Springer-Verlag, 2008. doi:10.1007/978-0-387-49970-3.
[38] Turing A. On Computable Numbers, with an Application to the Entscheidungs problem, Proc. London Math. Soc., 42-2, 1936, 230-265; A correction, ibid, 43, 1937, 544-546. doi:10.1112/plms/s2-42.1.230.
[39] Turing A. Systems of Logic based on Ordinals, Proc. London Math. Soc. Series 2, 45, 1939, 161-228. doi:10.1112/plms/s2-45.1.161.
[40] Turing, A. Intelligent Machinery, 1948, in Collected Works of A.M. Turing: Mechanical Intelligence, ed.D.C.Ince, Elsevier Science, 1992.
[41] 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.
[42] Whitehead AN, Russell B. Principia Mathematica, vol.1, 1910, ISBN-10:1603861823, 13:978-1603861823. vol.2, 1912, https://www.slideshare.net/Kadio3/insurance-250661884, vol.3, 1913, Cambridge Univ. Press, London.

Typ dokumentu

Bibliografia

Identyfikator YADDA

bwmeta1.element.baztech-c74e0f5c-96cf-40a4-ac9b-0209b6835099