🚀 go-pugleaf

There's a very nice theorem by Charles Bennett that shows that every 1-1
recursive function can be computed by a TM whose transition function is
invertable.  Moreover, the total space involved in the simulation is
quadratic, i.e., if the original machine runs in space s(n), the simulation
runs in space s^2(n).  Bennett's motivation for this work had to do with
thermodynamics(!), specifically, do the laws of thermodynamics entail
direct limits on computation?  His result shows that they do not.

Fenner used Bennett's theorem to prove the following, which is half of a
complexity theoretic analog to Cantor-Bernstein/Myhill:

	If every polynomial time 1-degree consists of a single polynomial
	time isomorphism type, then P = PSPACE.

Royer and I (using technology that doesn't depend on reversibility)
established the converse.  This appeared in FOCS:

	Every Polynomial-Time 1-Degree Collapses iff P = PSPACE,
	Fenner, Kurtz, Royer. Proc. 30th IEEE Symp. Foundation of
	Comp. Sci. (1989), p.624-629.

Stu