Класс DSPACE(s(n)), означает класс задач,
разрешимых на машине Тьюринга,
использующей не более s(n) ячеек.
Более формально:
Язык принадлежит классу ,
если существует машина ТьюрингаT, разрешающая данный язык, и число используемых ею ячеек ленты на входе длины n не превышает s(n).
Внимание! Данная статья выбрана для репликации во внешнюю базу знаний компании. Пожалуйста, не допускайте в этой статье публикацию конфиденциальной информации, ведения обсуждений в теле статьи, и более ответственно относитесь к качеству самой статьи — проверяйте орфографию, пишите по-русски, избегайте непроверенной вами информации.
