# constructible

## Primary tabs

Defines:
time constructible, space constructible
Type of Math Object:
Definition
Major Section:
Reference

## Mathematics Subject Classification

68Q15 Complexity classes (hierarchies, relations among complexity classes, etc.)

### Time constructible definition?

What do you mean "there exists a turing machine that halts after using exactly f(n) cells?" For any value of f(n), I can construct a turing machine that halts after f(n) steps.

Did you mean halts after f(n) steps on input n? Or something like this?

### Re: Time constructible definition?

The quote you give does not appear in this entry. What it says is "when $T$ receives as input the a series of $n$ ones, it halts after exactly $f(n)$ steps"

### Computable functions

if i have a computable function f how can i prove there exists g>=f which is time constructible?

### Re: Computable functions

Off the top of my head, it should work, on input n, compute f(n), then wait f(n) steps, then terminate.

### Re: Computable functions

This was my idea too. So for computable f g would be the running time of an M which does what you said.

Am I correct that a time constructible function g is a function for which TIME(g) != empty-set (i.e. it's a running time function for some TM)?

thanks

### Re: Computable functions

That's exactly the definition of a time constructible function.