time hierarchy theorem
the time hierarchy theorem shows that allowing turing machines more computation time strictly increases the set of languages that they can decide. we restrict attention to time-constructible functions 
, which means that the mapping 
can be computed in 
time.
the proof provided for the time hierarchy theorem in arora's is quite simple but it may take a few reads to grasp.
, which means that the mapping can be computed in time.
the proof provided for the time hierarchy theorem in arora's is quite simple but it may take a few reads to grasp.
if 
are time-constructible functions satisfying 
, then
[cite:;taken from @computability_arora_2009 theorem 3.1]
are time-constructible functions satisfying , then
[cite:;taken from @computability_arora_2009 theorem 3.1]to showcase the essential idea of the proof of the-time-hier with minimal notation, we prove the simpler statement 
.
consider the following Turing machine
: "on input 
, run for 
steps the universal TM 
to simulate the execution of 
on . if outputs some bit 
in this time, then output the opposite answer (i.e., output 
). else output 0." here is the machine represented by the string .
by definition, halts within 
steps and hence the language 
decided by is in 
. we claim that 
. for contradiction's sake, assume that there is some TM 
and constant 
such that TM , given any input 
, halts within 
steps and outputs 
.
the time to simulate by the universal Turing machine on every input is at most 
for some number 
that depends on the alphabet size and number of tapes and states of 
but is independent of 
. there is some number 
such that 
for every 
. let be a string representing the machine whose length is at least (such a string exists since is represented by infinitely many strings). then, will obtain the output 
within steps, but by definition of , we have 
. thus we have derived a contradiction.
the proof of the-time-hier for general is similar and uses the observation that the slowdown in simulating a machine using is at most logarithmic.
[cite:;taken from @computability_arora_2009 chapter 3.1 time hierarchy theorem]
.
consider the following Turing machine
: "on input , run for steps the universal TM to simulate the execution of on . if outputs some bit in this time, then output the opposite answer (i.e., output ). else output 0." here is the machine represented by the string .
by definition,
halts within steps and hence the language decided by is in . we claim that . for contradiction's sake, assume that there is some TM and constant such that TM , given any input , halts within steps and outputs .
the time to simulate
by the universal Turing machine on every input is at most for some number that depends on the alphabet size and number of tapes and states of but is independent of . there is some number such that for every . let be a string representing the machine whose length is at least (such a string exists since is represented by infinitely many strings). then, will obtain the output within steps, but by definition of , we have . thus we have derived a contradiction.
the proof of the-time-hier for general
is similar and uses the observation that the slowdown in simulating a machine using is at most logarithmic.
[cite:;taken from @computability_arora_2009 chapter 3.1 time hierarchy theorem]
- for any
, 
: here 
, 
. since 
, this implies an infinite hierarchy within 
. -
: let for any . let 
. then 
. 
. so, 
. since this holds for any 
, 
. (note: 
is usually defined as 
. the claim holds as 
is in 
and 
is polynomial.)
we construct a language such that 
but 
.
define a DTM:
on input:
time on . since 
, runs in 
time. thus 
.
assume for contradiction
. then 
such that 
and 
runs in 
time.
consider input
. 
simulates 
. if accepts, rejects. if rejects, accepts. so 
, which contradicts 
. thus, 
.
some technicalities:
such that but .
define a DTM
:
on input
:
- if is not an encoding of a TM
, reject. - simulate on input (i.e.,
) for at most 
steps of . - if accepts within these steps, rejects.
- if rejects or does not halt within steps, accepts.
time on . since , runs in time. thus .
assume for contradiction
. then such that and runs in time.
consider input
. simulates . if accepts, rejects. if rejects, accepts. so , which contradicts . thus, .
some technicalities:
- padding: to handle constant factors in simulation overhead and ensure the asymptotic condition applies, one can use a padding argument. any TM can be converted to an equivalent
with a longer encoding 
such that the asymptotics hold. - time-constructibility of \(g(n)\): needs to compute
to use as a step counter for the simulation. this computation takes time and doesn't dominate 's runtime. - simulation overhead: the
factor is a standard overhead for simulating a TM on a universal TM. more advanced models or simulations can sometimes improve this.
and 
be 
, then
