DSPACE

Материал из свободной русской энциклопедии «Традиция»
Перейти к: навигация, поиск

Класс DSPACE(s(n)), означает класс задач, разрешимых на машине Тьюринга, использующей не более \(s(n)\) ячеек.

Более формально:

Язык \(L \subset \Sigma^*\) принадлежит классу \({\cal DSPACE}(s(n))\), если существует машина Тьюринга \(T\), разрешающая данный язык, и число используемых ею ячеек ленты на входе длины \(n\) не превышает \(s(n)\).


По крайней мере часть этого текста взята с ресурса http://lib.custis.ru/ под лицензией GDFL.Список авторов доступен на этом ресурсе в статье под тем же названием.