[FOM] A Newtonian computing design

Robert M. Solovay solovay at math.berkeley.edu
Tue Feb 24 00:51:02 EST 2004

On Wed, 11 Feb 2004, Harvey Friedman wrote:

> 1. The goal is to determine whether any given Turing machine with at most
> 100 quadruples eventually halts at the empty tape input.

	I'm puzzled by the use of "quadruples" here. Usually TM's are
presented with quintuples:

{State, Symbol} --> {New State, New Symbol, Direction to shift}.

	If I had to guess, I'd suspect that in the quadruple, either a
direction to shift *or* a new symbol to print is included as the last

	Any reason behind the shift from quintuples to quadruples?

	--Bob Solovay

More information about the FOM mailing list