 |
| Russian | English |
| функция, конструируемая по времени | time-constructable function (функция Т(п), такая, что некоторая детерминированная машина Тьюринга при данном входе длины n делает ровно Т(n) шагов до своей остановки) |
| функция, конструируемая по памяти | space constructible function (функция S(n) такая, что если некоторая детерминированная машина Тьюринга, начав работу над данным входом длины и, поместит специальный маркёр на S(n)-m клетку одной из своих лент, просмотрев не более S(n) клеток на каждой ленте) |