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