Computation: computability, similarity, and duality

Front Cover
Pitman, 1986 - Mathematics - 236 pages
0 Reviews

What people are saying - Write a review

We haven't found any reviews in the usual places.

Contents

FINITE AUTOMATA AND COMPUTABILITY
5
The Turing Machine
17
Recursive Functions
27
DETERMINISTIC SIMILARITY
44
16 Resources of the Multitape Turing Machine
46
17 Basic Relationships and Properties
59
18 LogSpace Transform Machine
65
19 LogSpace Constructible Graphs and Nice Pair of Functions
68
32 PRAM
144
33 The Similarity Between PRAM UA UC and Other Models
147
34 Some Remarks on Similarity
151
COMPUTATIONAL TYPES AND DUALITY
159
36 The Logical Computational Types for TM
165
37 The Classification of Logical Computational Types
169
38 Alternating Turing Machines
175
General Computational Types
181

20 The Concept of Similarity
76
MultiIndex Random Access Machine
80
22 Examples
88
23 RAM Simulating TM
94
24 LSTM Simulating RAM
96
Vector Machines
102
26 Examples
106
27 Matrix Transpose and Word Projection
117
Simulating LSTM
125
29 The Similarity Between VM RAM and TM
133
Other Parallel Computational Models
136
31 Uniform Aggregates
142
40 General Computational Types
185
41 Restrictions
188
42 The Third Similarity Theorem and Complexity Classes
194
43 The Majority and Random Types
197
44 Complete Problems
205
The Duality Between Parallel Time and Space
210
46 The Symmetry Theorem and Restriction Theorem
212
47 The Complexity of Formal Proof
217
REFERENCES
228
INDEX
232
Copyright

Other editions - View all

Bibliographic information