Si adicionalmente, existe una Máquina de Turing tal que toda entrada de longitud "n" utiliza exactamente "S"("n") casillas, se dice que la función "S" es de espacio completamente constructivo.