função construível
Sign in to savefunction whose values can be computed in a number of steps or a number of Turing-machine cells of order given by the function itself
Article · Português
Na teoria da complexidade, uma função tempo-construível é uma função f dos números naturais para números naturais com a propriedade de que f(n) pode ser construída a partir de n por uma máquina de Turing em tempo de ordem f(n). A finalidade de tal definição é excluir funções que não provêm um limitante superior sobre o tempo de execução de alguma máquina de Turing.
Abstract from DBpedia / Wikipedia · CC BY-SA