A Note on Square Rooting of Time Functions of Turing Machines.

Saved in:

Bibliographic Details
Title:	A Note on Square Rooting of Time Functions of Turing Machines.
Authors:	Lipton, Richard J., Ogihara, Mitsunori, Zalcstein, Yechezkel
Source:	Theory of Computing Systems. May2003, Vol. 36 Issue 3, p295. 5p.
Subjects:	Machine theory, Square root, Mathematical functions, Mathematics
Abstract:	This article focuses on square rooting of time functions of Turning machines. It studies the conjecture that for all nondeterministic time functions T the square root of T is equivalent to the time function of a nondeterministic Turning machines. Mathematical studies show that deterministic version of this conjecture is false.
Database:	Engineering Source

Description
Abstract:	This article focuses on square rooting of time functions of Turning machines. It studies the conjecture that for all nondeterministic time functions T the square root of T is equivalent to the time function of a nondeterministic Turning machines. Mathematical studies show that deterministic version of this conjecture is false.
ISSN:	14324350
DOI:	10.1007/s00224-002-1079-x