The quantitative aspects of one-tape Turing machine computations are considered. It is shown, for instance, that there exists a sharp time bound which must be reached for the recognition of ...nonregular sets of sequences. It is shown that the computation time can be used to characterize the complexity of recursive sets of sequences, and several results are obtained about this classification. These results are then applied to the recognition speed of context-free languages and it is shown, among other things, that it is recursively undecidable how much time is required to recognize a nonregular context-free language on a one-tape Turing machine. Several unsolved problems are discussed.
In this paper we study diagonal processes over time-bounded computations of one-tape Turing machines by diagonalizing only over those machines for which there exist formal proofs that they operate in ...the given time bound. This replaces the traditional "clock" in resource bounded diagonalization by formal proofs about running times and establishes close relations between properties of proof systems and existence of sharp time bounds for one-tape Turing machine complexity classes. Furthermore, these diagonalization methods show that the Gap Theorem for resource bounded computations does not hold for complexity classes consisting only of languages accepted by Turing machines for which it can be formally proven that they run in the required time bound.
Some general results about hierarchies of undecidable problems in automata theory are given, and studies are described which show how properties of sets accepted by automata (i.e. languages) change ...from decidable to undecidable problems as the computational power of the automata is increased. This work also yields unified techniques which characterize for different languages large classes of undecidable problems.
The purpose of this note is to show that it is recursively undecidable how much tape is required by a Turing machine to recognize nonregular context-free languages.
Computing the Future National Research Council; Computer Science and Telecommunications Board; Committee to Assess the Scope and Direction of Computer Science and Technology
1992, 1992-01-01
eBook
Computers are increasingly the enabling devices of the information revolution, and computing is becoming ubiquitous in every corner of society, from manufacturing to telecommunications to ...pharmaceuticals to entertainment. Even more importantly, the face of computing is changing rapidly, as even traditional rivals such as IBM and Apple Computer begin to cooperate and new modes of computing are developed.Computing the Future presents a timely assessment of academic computer science and engineering (CS&E), examining what should be done to ensure continuing progress in making discoveries that will carry computing into the twenty-first century. Most importantly, it advocates a broader research and educational agenda that builds on the field's impressive accomplishments.The volume outlines a framework of priorities for CS&E, along with detailed recommendations for education, funding, and leadership. A core research agenda is outlined for these areas: processors and multiple-processor systems, data communications and networking, software engineering, information storage and retrieval, reliability, and user interfaces.This highly readable volume examinesComputer science and engineering as a discipline--how computer scientists and engineers are pushing back the frontiers of their field.How CS&E must change to meet the challenges of the future.The influence of strategic investment by federal agencies in CS&E research.Recent structural changes that affect the interaction of academic CS&E and the business environment.Specific examples of interdisciplinary and applications research in four areas: earth sciences and the environment, computational biology, commercial computing, and the long-term goal of a national electronic library.The volume provides a detailed look at undergraduate CS&E education, highlighting the limitations of four-year programs, and discusses the emerging importance of a master's degree in CS&E and the prospects for broadening the scope of the Ph.D. It also includes a brief look at continuing education.
The object of this paper is to study the realization of a sequential machine from several smaller machines. The basic tools in this investigation are the partitions with the substitution property and ...the partition pairs. It is shown that to every (loop-free) realization of a sequential machine from
n smaller machines corresponds a set of
n partitions with the substitution property whose product is the zero partition. Conversely, it is shown that to every such set of
n partitions corresponds a realization of the given sequential machine from
n smaller machines. The natural ordering of these partitions is reflected in the information flow between the corresponding component machines and the algebraic operations defined between these partitions corresponding to the realization, govern the modifications of this realization. Finally, it is shown how the amount of information flowing between the component machines in a realization can be studied by means of partition pairs.
In this note we define the amount of feedback in a realization of a sequential machine M, give a simple algorithm to compute the minimal amount of feedback which has to be present in any realization ...of M, and give a canonical realization of M which uses the minimal amount of feedback.
PDF
