Undecidability in the Imitation Game

Authors: Sato Y.¹; Ikegami T.²

Source: Minds and Machines, Volume 14, Number 2, May 2004 , pp. 133-143(11)

Publisher: Springer

Buy & download fulltext article:

Price: $47.00 plus tax (Refund Policy)

Abstract:

This paper considers undecidability in the imitation game, the so-called Turing Test. In the Turing Test, a human, a machine, and an interrogator are the players of the game. In our model of the Turing Test, the machine and the interrogator are formalized as Turing machines, allowing us to derive several impossibility results concerning the capabilities of the interrogator. The key issue is that the validity of the Turing test is not attributed to the capability of human or machine, but rather to the capability of the interrogator. In particular, it is shown that no Turing machine can be a perfect interrogator. We also discuss meta-imitation game and imitation game with analog interfaces where both the imitator and the interrogator are mimicked by continuous dynamical systems.

Keywords: analog computation; dynamical systems; imitation game; Turing machine; undecidability

Document Type: Research article

DOI: http://dx.doi.org/10.1023/B:MIND.0000021747.28850.16

Affiliations: 1: Brain Science Institute, Institute of Physical and Chemical Research (RIKEN), 2-1 Hirosawa, Wako, Saitama 351, Japan Corresponding author 2: Graduate School of Arts and Science, University of Tokyo, 3-8-1 Komaba, Meguro-ku, Tokyo 153, Japan

Publication date: 2004-05-01