Turning Test as a Defining Feature of AI-Completeness

153
abstract whitepaper - Turning Test as a defining feature of AI-completeness

Reprinted with permission from Roman V. Yampolskiy, Ph.D

Abstract. The paper contributes to the development of the theory of AICompleteness by formalizing the notion of AI-Complete and AI-Hard problems.
The intended goal is to provide a classification of problems in the field of General Artificial Intelligence. We prove Turing Test to be an instance of an AI-Complete problem and further show certain AI problems to be AI-Complete or AI-Hard via polynomial time reductions. Finally, the paper suggests some directions for future work on the theory of AI-Completeness.

Keywords: AI-Complete, AI-Easy, AI-Hard, Human Oracle.

1 Introduction

Since its inception in the 1950s the field of Artificial Intelligence has produced some unparalleled accomplishments while at the same time failing to formalize the problem space it is concerned with. This paper proposes to address this shortcoming by extends on the work in [56] and contributing to the theory of AICompleteness, a formalism designed to do for the field of AI what notion of NP-Completeness did for computer science in general. It is our belief that such formalization will allow for even faster progress in solving remaining problems in humankind’s conquest to build an intelligent machine.

According to the encyclopedia Wikipedia the term “AI-Complete” was proposed by Fanya Montalvo in the 1980s [54]. A somewhat general definition of the term included in the 1991 Jargon File [37] states:

AI-Complete: [MIT, Stanford, by analogy with NP-complete'] adj. Used to describe problems or subproblems in AI, to indicate that the solution presupposes a solution to thestrong AI problem’ (that is, the synthesis of a human-level intelligence). A problem that is AI-complete is, in other words, just too hard. Examples…

Full Whitepaper Here

Subscribe

* indicates required
Next articleKeeping Your Goals in Focus
Dr. Roman V. Yampolskiy is a Tenured Associate Professor in the department of Computer Science and Engineering at the Speed School of Engineering, University of Louisville. He is the founding and current director of the Cyber Security Lab and an author of many books including Artificial Superintelligence: a Futuristic Approach. During his tenure at UofL, Dr. Yampolskiy has been recognized as: Distinguished Teaching Professor, Professor of the Year, Faculty Favorite, Top 4 Faculty, Leader in Engineering Education, Top 10 of Online College Professor of the Year, and Outstanding Early Career in Education award winner among many other honors and distinctions. Yampolskiy is a Senior member of IEEE and AGI; Member of Kentucky Academy of Science, and Research Associate of GCRI.