2.3. Oracles 1. Denote by oracle the content of the oracle interface tape, the cells on which contain symbols from .

2. Denote by  the oracle that contains the lexicographic ordered notations  for all TMs  and  such that  recognizes .

3. Denote by  the blank oracle.

## 2.4. Oracle Turing Machines

1. We shall understand the construction from Item 2.2.1, where the oracle interface tape may be non-blank, as oracle Turing machine (OTM). Denote OTM by , where  is TM and  is oracle
(thus  = ).

2. Extending the concepts from Items 2.2.3 and 2.2.4 to OTMs, we call OTMs  and as -similar if for every  ≤  and for any questions β = 1
, … , 
the equality () = () holds. 

Two OTMs  and , which are -similar for every  ∈ ℕ, we call similar and denote this by  ≈ .

3. We say that OTM  reduces to TM  if  ≈ . Denote the type of OTM by notation ≻ if OTM reduces to some TM and in another case use the notation ⊁.

2.5. Testers 1. Any pair , , where  and  are OTMs, we call the tester. For the specified tester we call the interrogator, and  the second participant (SP).

2. Denote the tester type by notation (type of interrogator, type of SP).

3. We say that interrogator is dumb if its answer to any consequence of questions is .

2.6. Tests 1. Consider tester  = , and TM  and define the following procedure as the left 
(the right) test:
 At the beginning of the test, the question  enters the interrogator  input.

 Each answer of interrogator serves as the question for both  and  (we call such a question the test question).

 The question αα (or the question αα for the right test), where α and α are the answers of  and  to the last test question, enters  input. We interpret this as receiving the first test answer from the "left" subject of the test, and receiving the second test answer from the "right" one. 

 Whenever  has reached the final state marked with "Left" ("Right"), the test is finished and the result of the test is "SP is on the left" ("SP is on the right").

Denote by ,,, ℓ- (by ,,, -) the left (the right) test described above and denote by ,,,∗- any of these tests.

2. We say that:
 TM  fails the left test , , ,, ℓ- (the right test , ,  ,, -) if either  does not answer some test question that SP  has answered or if this test is finished with the correct result.

 TM fails the test ,,- if it fails both the left test ,,, ℓ- and the right test ,, , -
2.

The statement that TM  fails the test ,,- we denote in short by  ⋫ ; the converse statement we denote by  ⊳ .

3. We say that tester  is successful for a given set  ⊆  if ∀∈
( ⋫ ).

4. Assign to each SP  ∈  the dumb interrogator ℑ ∈  who completes the test ℑ
,  ,,∗ for any oracle  only in the case when the test answers from  and  are different, and in this case ℑ
calculates α = (
), where  is a number of the current test step, and indicates the location of SP as the source of reply α. Note that ℑ
performs operations that do not depend on .

Put 
 ≝ ℑ
,  and 
 ≝ 
:  ∈  .

2.7. Comments 1. The handling of every question by certain TM with the input head and the output head can be described as the functioning of an arbitrary TM with only one head and with initial content of the 
 
2 See also the strict test in Section 5.