-2

I'm asked to prove that the measure $\Gamma_e(x) = s ~ ~ \iff ~ ~ \varphi_e(x)$ uses exactly $s$ work tape cells (i.e. once it halts, the number of tape cells used by a Turing machine to compute it is equal to $s$) is a complexity measure wrt Blum's axioms.

I've proven that it meets the first axiom, i.e. $\Gamma_e(x)$ is defined if and only if $\varphi_e(x)$ halts, but I'm confused about how exactly the second axiom is met. I've seen that if we consider the number of steps taken by a TM instead, then the second axiom holds because the question "does $\varphi_e(x)$ halt in exactly $s$ steps" is decidable - simply run the TM for $s$ steps and find out if it halted on the last step or not. But how does this work for space? I can think of a TM that only takes one tape cell yet never halts, and so the question "does this TM use exactly 2 tape cells" would be undecidable apparently.

Can someone tell me where I've gone wrong? How is it possible that this is a complexity measure?

Thomas
  • 932

1 Answers1

1

I'm not familiar with your notation, but for any particular natural $k$ there are finitely many possible strings of that length and if the TM encounters the same string twice on its tape then it will never halt. So we can simulate the TM and track all strings it has seen, and make sure that it never exceeds its allotted space, and can thus decide if it halts.

user21820
  • 57,693
  • 9
  • 98
  • 256
  • Ah, so the idea is that if the TM takes unbounded space, then we can reject it in finite time as soon as it exceeds the required space, and if the TM takes bounded space then there are only finitely many states in which the TM can be? That's clever, I'll try it out, thanks! – Thomas May 15 '14 at 07:05
  • @Thomas: Right! – user21820 May 15 '14 at 07:06