Notes

Chapter 12: The Principle of Computational Equivalence

Section 8: Undecidability and Intractability


Properties [of example Turing machines]

The maximum numbers of steps increase with input size according to:

(a) 14*2^Floor[n/2]-11+2Mod[n, 2]

(b) (does not halt for x=1)

(c) 2^n-1

(d) (7(1+Mod[n,2])4^Floor[n/2]+2Mod[n,2]-7)/3

(h) (see note below)

(i) (does not halt for various x>53)

(j) (does not halt for various x>39)

(k) (does not halt for x=1)

(l) 5*(2^(n-2)-1)


From Stephen Wolfram: A New Kind of Science [citation]