The Bacta Review   A New Kind of Science
The German computer pioneer Konrad Zuse is said to have put forward similar ideas before Fredkin, but I have not examined any of the relevant writings.

For an engaging popular account of Fredkin and his ideas, see Robert Wright's "Did the Universe Just Happen?" (Atlantic Monthly, April 1988), an excerpt from Wright's book Three Scientists and Their Gods.