
## A Formalization Of The Turing Test Evgeny Chutchev 1. Introduction

The Turing test was described by A. Turing in his paper [4] as follows: An interrogator questions both Turing machine and second participant of the test (a person), each of which tries to appear human. The interrogator does not know from whom exactly he receives answers and has the objective to tell the Turing machine from the person (for more details, see, for example, [3]).

In this paper, we consider a formalization of the Turing test and obtain the following results (Figure 1.1):

![0_image_0.png](0_image_0.png)

Figure 1.1. Summary of results
The rest of the paper is organized as follows:
Section 2 gives definitions and introduces notations. Section 3 considers tests with arbitrary Turing machines. Section 4 considers tests with Turing machines of some special classes. Section 5 considers the strict Turing test.

Section 6 presents the conclusion.

Section 7 contains a list of definitions and notations.

Section 8 contains references.

Section 9 is an appendix, where we consider a random answers model for the second participant of the test that does not follow an algorithm.

## 2. General Definitions And Notations

2.1. Words and numbers 1. Suppose  is a finite alphabet and symbol θ does not belong to . By 
∗ denote all words over , including the empty word λ. By λ denote the sequence of  empty words λ.

2. Denote by ℕ the set of all natural numbers (excluding zero), and put ℕ0 ≝ ℕ ∪ {0}. We will not make any distinction between the elements of ℕ0 and their notations over the alphabet , 
assuming ℕ0 = 
∗\*λ+.

3. Fix some letter  ∈ , and for each word ω ∈ 
∗ denote by ω the word ω.