RUS  ENG
Full version
JOURNALS // Izvestiya Vysshikh Uchebnykh Zavedenii. Matematika // Archive

Izv. Vyssh. Uchebn. Zaved. Mat., 2014 Number 9, Pages 80–86 (Mi ivm8933)

Brief communications

Computational power of real-time Turing machines with sublogarithmic memory restrictions

A. N. Leshchev

Chair of Theoretical Cybernetics, Kazan (Volga Region) Federal University, 18 Kremlyovskaya str., Kazan, 420008 Russia

Abstract: In this paper we consider the well-known Turing machine model – nondeterministic real-time Turing machine. We prove the existence of nonregular complexity classes of languages that can be recognized by nondeterministic real-time Turing machines with sublogarithmic memory restrictions. These complexity classes form a strict hierarchy. We define a special language family and show its properties to prove that hierarchy.

Keywords: real-time Turing machine, nondeterministic Turing machine, memory restrictions.

UDC: 519.7

Presented by the member of Editorial Board: N. K. Zamov
Received: 01.04.2014


 English version:
Russian Mathematics (Izvestiya VUZ. Matematika), 2014, 58:9, 66–70

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024