Hao Wang
- 1 A. M. TURING, On computable numbers, Proc. London Math. Soc., Series 2, 24 (1936), 230--265.Google Scholar
- 2 S. C. KLEENE:, Introduction to Metamathematics, 1952.Google Scholar
- 3 A. W. BURKS and I. M. CoPI, The logical design of an idealized general-purpose computer, J. Franklin Inst., 261 (1956), 299-314, 421-436.Google Scholar
- 4 E. F. MOORE, A simplified universal Turing machine, Proc. ACM, Sept. 8, 1952, 1953. Google Scholar
Index Terms
- A Variant to Turing's Theory of Computing Machines
Recommendations
Theory of one-tape linear-time Turing machines
A theory of one-tape two-way one-head off-line linear-time Turing machines is essentially different from its polynomial-time counterpart since these machines are closely related to finite state automata. This paper discusses structural-complexity issues ...
Some properties of one-pebble turing machines with sublogarithmic space
This paper investigates some aspects of the accepting powers of deterministic, nondeterministic, and alternating one-pebble Turing machines with spaces between log log n and log n. We first investigate a relationship between the accepting powers of two-...
Weight-reducing Turing machines
AbstractIt is well known that one-tape Turing machines running in linear time are no more powerful than finite automata; namely they recognize exactly the class of regular languages. We prove that it is not decidable if a one-tape machine runs in linear ...
Comments