1. Introduction2. The Question3. The AnswerReferencesCAN A TURING PLAYER IDENTIFY ITSELF?DAVID K. LEVINE AND AND BALÁZS SZENTESABSTRACT. We show that the problem of whether two Turing Machinesare functionally equivalent is undecidable and explain why this is signif-icant for the theory of repeated play and evolution.Keywords: Economic Theory, Game Theory.JEL Classification: A1; A21. INTRODUCTIO NConsider the basic problem of cooperation in a Prisoner’s dilemma typesituation. Cooperative outcomes must be enforced by punishing free-riders- to do so it is necessary to identify free-riders so that they can be punished.This observation is a feature of the literature on repeated play with boundedrationality and in the theory of the evolution of cooperation. In both cases,a “good” strategy is to give some sort of “secret handshake” to determineif the opponent is of the same type - and so should be cooperated with -or a different type that should be punished. In the setting of play betweenfinite state machines, the “handshake” is described in Rubinstein [1986]; inthe evolutionary setting by Robson [1990]. Typically, these “secret hand-shakes” take the form of some sort of signalling during the course of play,but any strategy must be generated by an algorithm, and in some circum-stances it may be able to inspect the opponents algorithm prior to play -this has obvious advantages over testing the opponent during the course ofplay. An explicit theory along these lines can be found in Levine and Pe-sendorfer [2002]. Of course an algorithm may be described in many ways- from a strategic perspective, what is important is not details of the al-gorithm, but rather its functionality. Is my opponent going to cheat, so Ishould do likewise? Is he going to engage in a strategy that leaves him opento exploitation?Date: First Version: 20th January 2006, This Version: 16th March 2006.UCLA and The University of Chicago. Corresponding Author - David K Levine: De-partment of Economics, UCLA, Los Angeles, CA 90095, USA. Phone/Fax: 310-825-3810.Email: [email protected]. Balász Szentes: Department of Economics, The Universityof Chicago, 1126 59th Street, Chicago, IL 60637. Email: [email protected] thank National Science Foundation Grants SES-03-14713 and SES-05-18762 forfinancial support.1CAN A TURING PLAYER IDENTIFY ITSELF? 2The purpose of this note is to examine the extent to which it is possible toidentify an algorithm based on its function, rather than on its description.1Anatural way to describe algorithms is as a Turing Machine. Binmore [1990]and Anderlini [1990] were among the first to model players as Turing Ma-chines. In their models, machines receive a description of their opponentand the game played as inputs. The authors show that there does not existsa machine which always gives the best response to the opponent’s strategy.2In this note we do not require Turing Machines to predict the strategies oftheir opponents. We merely want to know if the strategy of a Turing Ma-chine can determine whether its opponent is equivalent to itself. In otherwords: Are there Turing machines that can recognize whether their oppo-nents are computationally equivalent to themselves?2. THE QUESTIONWe let τ denote a Turing Machine, and τ(x) denote the output of τ oninput x, where τ (x) = ∞ if τ doesn’t halt on x. By convention since thereare countably many Turing Machines, we identify their descriptions withintegers. We let hτi denote the description of the Turing Machine τ. Inother words τ0(hτi) is the output of the Turing Machine τ0when the input isthe description of the Turing Machine τ. If we have two Turing Machinesτ1and τ2we say that they are equivalent if they compute the same function,that is τ1(x) = τ2(x) for all x. We say that a Turing Machine is finite if ithalts on every input.We consider the following questions, and prove that the answer is no toall of them.Question 1: Is it a decidable problem whether two Turing Machines areequivalent?Question 2: Is it a decidable problem whether two finite Turing Ma-chines are equivalent?Question 3: Is there some Turing Machine τ for which it is a decidableproblem whether a Turing Machine is equivalent to τ?Question 4: Is there some finite Turing Machine τ for which it is a de-cidable problem whether another finite Turing Machine is equivalent to τ?Recall that for example the problem posed in Question 1 is said to bedecidable if there is a Turing Machine τ∗such that τ∗(hτi, hτ0i) = 1 if τ andτ0are equivalent and 0 if they are not.1An alternative approach is to consider Bayesian priors as in Nachbar [1997].2Canning [1992] shows that if the domain of possible players and games are appro-priately restricted then Turing Machines will play Nash Equilibria. These restrictions arefairly severe.CAN A TURING PLAYER IDENTIFY ITSELF? 33. THE ANSWEROur point of departure is the basic result that determining whether or not aTuring Machine halts is not a decidable problem - that is, there is no TuringMachine which can take as input the description of a Turing Machine and aninteger n and compute 1 if it halts on n and 0 if it does not. More precisely,from the proof of the Halting Lemma whether τ (hτi) halts or not is notdecidable. For expositional purposes we provide a proof for this result.Halting Lemma. Whether a Turing Machine halts on itself is undecidable.3Proof. Suppose by contradiction, that there exists a Turing Machine τ∗suchthat τ∗(hτi) = 1 if τ (hτi) halts and zero otherwise. Construct the TuringMachine τ0as follows.τ0(hτi) =0 if τ∗(hτi) = 0∞ if τ∗(hτi) = 1.Then τ0(hτ0i) = 0 ⇔ τ∗(hτ0i) = 0 by the construction of τ0. However, by thedefinition of τ∗, τ∗(hτ0i) = 0 is true if and only if τ0does not halt, that is,τ0(hτ0i) = ∞. So τ0(hτ0i) = 0 ⇔ τ0(hτ0i) = ∞ an obvious contradiction. We now answer each question in the negative by showing that if it hada positive answer then we could find a Turing Machine that determineswhether τ (hτi) halts for any Turing Machine τ, contradicting the fact thatthis problem is undecidable.Answer to Question 1: Fix a Turing Machine τ. Define τ0as follows.If x 6= hτi then τ0(x) = τ (x). If x = hτi then τ0(hτi) = ∞. To construct τ0is easy. It is almost identical to τ, except that first it checks whether theinput is hτi or not. If it is, it runs forever, otherwise it simulates τ. Notice,that in order to define τ0one