The DOI matches its Crossref record.
Computation: Finite and Infinite Machines.
Abstract
From the Preface (See Front Matter for full Preface) Man has within a single generation found himself sharing the world with a strange new species: the computers and computer-like machines. Neither history, nor philosophy, nor common sense will tell us how these machines will affect us, for they do not do work as did machines of the Industrial Revolution. Instead of dealing with materials or energy, we are told that they handle control and information and even intellectual processes. There are very few individuals today who doubt that the computer and its relatives are developing rapidly in capability and complexity, and that these machines are destined to play important (though not as yet fully understood) roles in society's future. Though only some of us deal directly with computers, all of us are falling under the shadow of their ever-growing sphere of influence, and thus we all need to understand their capabilities and their limitations. It would indeed be reassuring to have a book that categorically and systematically described what all these machines can do and what they cannot do, giving sound theoretical or practical grounds for each judgment. However, although some books have purported to do this, it cannot be done for the following reasons: a) Computer-like devices are utterly unlike anything which science has ever considered---we still lack the tools necessary to fully analyze, synthesize, or even think about them; and b) The methods discovered so far are effective in certain areas, but are developing much too rapidly to allow a useful interpretation and interpolation of results. The abstract theory---as described in this book---tells us in no uncertain terms that the machines' potential range is enormous, and that its theoretical limitations are of the subtlest and most elusive sort. There is no reason to suppose machines have any limitations not shared by man.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cited by
Statistical mechanics of cellular automata
Wolfram, S. (1983) · Reviews of Modern Physics · doi:10.1103/revmodphys.55.601 · Cited by 3,114
Universality and complexity in cellular automata
Wolfram, S. (1984) · Physica D: Nonlinear Phenomena · doi:10.1016/0167-2789(84)90245-8 · Cited by 1,914
A lattice model of secure information flow
Denning, D. E. (1976) · Communications of the ACM · doi:10.1145/360051.360056 · Cited by 1,907
Swarm robotics: a review from the swarm engineering perspective
Brambilla, M., Ferrante, E., Birattari, M., & Dorigo, M. (2013) · Swarm Intelligence · doi:10.1007/s11721-012-0075-2 · Cited by 1,762
Newell, A. (1980) · Cognitive Science · doi:10.1207/s15516709cog0402_2 · Cited by 1,458
Steane, A. (1998) · Reports on Progress in Physics · doi:10.1088/0034-4885/61/2/002 · Cited by 1,391
Progress in supervised neural networks
Hush, D. R., & Horne, B. G. (1993) · IEEE Signal Processing Magazine · doi:10.1109/79.180705 · Cited by 1,247
Arguments concerning representations for mental imagery.
Anderson, J. R. (1978) · Psychological Review · doi:10.1037//0033-295x.85.4.249 · Cited by 1,232
Graves, A., Wayne, G., & Danihelka, I. (2014) · arXiv · doi:10.48550/arxiv.1410.5401 · Cited by 1,058
Blum, L., Shub, M., & Smale, S. (1989) · Bulletin of the American Mathematical Society · doi:10.1090/s0273-0979-1989-15750-9 · Cited by 1,056
Certification of programs for secure information flow
Denning, D. E., & Denning, P. J. (1977) · Communications of the ACM · doi:10.1145/359636.359712 · Cited by 1,029
A Theory of Program Size Formally Identical to Information Theory
Chaitin, G. J. (1975) · Journal of the ACM · doi:10.1145/321892.321894 · Cited by 849
Artificial Intelligence and the Modern Productivity Paradox: A Clash of Expectations and Statistics
Brynjolfsson, E., Rock, D., & Syverson, C. (2017) · National Bureau of Economic Research · doi:10.3386/w24001 · Cited by 773
A survey of computational complexity results in systems and control
Blondel, V. D., & Tsitsiklis, J. N. (2000) · Automatica · doi:10.1016/s0005-1098(00)00050-9 · Cited by 732
Artificial Intelligence, Automation and Work
Acemoglu, D., & Restrepo, P. (2018) · doi:10.3386/w24196 · Cited by 962
Computational Complexity of Probabilistic Turing Machines
Gill, J. (1977) · SIAM Journal on Computing · doi:10.1137/0206049 · Cited by 689
Computation theory of cellular automata
Wolfram, S. (1984) · Communications in Mathematical Physics · doi:10.1007/bf01217347 · Cited by 625
Integration of nanoscale memristor synapses in neuromorphic computing architectures
Indiveri, G., Linares-Barranco, B., Legenstein, R., Deligeorgis, G., & Prodromakis, T. (2013) · Nanotechnology · doi:10.1088/0957-4484/24/38/384010 · Cited by 613
An approach to the formal analysis of user complexity
KIERAS, D., & POLSON, P. G. (1999) · International Journal of Human-Computer Studies · doi:10.1006/ijhc.1983.0317 · Cited by 593
Information and computation: Classical and quantum aspects
Galindo, A., & Martín-Delgado, M. A. (2002) · Reviews of Modern Physics · doi:10.1103/revmodphys.74.347 · Cited by 552
An approach to the formal analysis of user complexity
Kieras, D., & Polson, P. G. (1985) · International Journal of Man-Machine Studies · doi:10.1016/s0020-7373(85)80045-6 · Cited by 504
Ullman, S. (1980) · Behavioral and Brain Sciences · doi:10.1017/s0140525x0000546x · Cited by 493
Random sequence generation by cellular automata
Wolfram, S. (1986) · Advances in Applied Mathematics · doi:10.1016/0196-8858(86)90028-x · Cited by 494
Artificial Intelligence, Automation, and Work
Acemoglu, D., & Restrepo, P. (2019) · The Economics of Artificial Intelligence · doi:10.7208/chicago/9780226613475.003.0008 · Cited by 478
Computational Mechanics: Pattern and Prediction, Structure and Simplicity
Shalizi, C. R., & Crutchfield, J. P. (2001) · Journal of Statistical Physics · doi:10.1023/a:1010388907793 · Cited by 471
Atchison, W. F., Conte, S. D., Hamblen, J. W., Hull, T. E., Keenan, T. A., Kehl, W. B., McCluskey, E. J., Navarro, S. O., Rheinboldt, W. C., Schweppe, E. J., et al. (1968) · Communications of the ACM · doi:10.1145/362929.362976 · Cited by 468
Computational capabilities of recurrent NARX neural networks
Siegelmann, H. T., Horne, B. G., & Giles, C. L. (1997) · IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics) · doi:10.1109/3477.558801 · Cited by 455
Studying the clinician: judgment research and psychological assessment
(1999) · Choice Reviews Online · doi:10.5860/choice.36-3045 · Cited by 444
Multinomial modeling and the measurement of cognitive processes.
Riefer, D. M., & Batchelder, W. H. (1988) · Psychological Review · doi:10.1037//0033-295x.95.3.318 · Cited by 434
Unpredictability and undecidability in dynamical systems
Moore, C. (1990) · Physical Review Letters · doi:10.1103/physrevlett.64.2354 · Cited by 414
Cognitive Systems and the Extended Mind
Rupert, R. D. (2009) · doi:10.1093/acprof:oso/9780195379457.001.0001 · Cited by 411
Why general artificial intelligence will not be realized
Fjelland, R. (2020) · Humanities and Social Sciences Communications · doi:10.1057/s41599-020-0494-4 · Cited by 399
Neural networks: An overview of early research, current frameworks and new challenges
Prieto, A., Prieto, B., Ortigosa, E. M., Ros, E., Pelayo, F., Ortega, J., & Rojas, I. (2016) · Neurocomputing · doi:10.1016/j.neucom.2016.06.014 · Cited by 391
Moore, C., & Mertens, S. (2011) · doi:10.1093/acprof:oso/9780199233212.001.0001 · Cited by 347
Dosi, G., & Egidi, M. (1991) · Journal of Evolutionary Economics · doi:10.1007/bf01224917 · Cited by 342
The induction of dynamical recognizers
Pollack, J. B. (1991) · Machine Learning · doi:10.1007/bf00114845 · Cited by 294
Chemical implementation of neural networks and Turing machines.
Hjelmfelt, A., Weinberger, E. D., & Ross, J. (1991) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.88.24.10983 · Cited by 256
The Turing Test: the first 50 years
French, R. M. (2000) · Trends in Cognitive Sciences · doi:10.1016/s1364-6613(00)01453-4 · Cited by 250
On the computational power of neural nets
Siegelmann, H. T., & Sontag, E. D. (1992) · Proceedings of the fifth annual workshop on Computational learning theory · doi:10.1145/130385.130432 · Cited by 238
Computability: An introduction to recursive function theory
Cutland, N. (1980) · doi:10.1017/cbo9781139171496 · Cited by 206
The Nature of Physical Computation
Shagrir, O. (2022) · doi:10.1093/oso/9780197552384.001.0001 · Cited by 70
THE NATURE OF HIERARCHICAL CONTROLS IN LIVING MATTER
Pattee, H. H. (1972) · Foundations of Mathematical Biology · doi:10.1016/b978-0-12-597201-7.50008-5 · Cited by 43
MARGOLUS, N. (1986) · Annals of the New York Academy of Sciences · doi:10.1111/j.1749-6632.1986.tb12451.x · Cited by 38
Necessary and Sufficient Conditions for Quantum Computation
Lloyd, S. (1994) · Journal of Modern Optics · doi:10.1080/09500349414552341 · Cited by 19
Metadata
- Authors
- Clarke, D. A., & Minsky, M. L.
- Venue
- The American Mathematical Monthly
- Publisher
- JSTOR
- Published
- 1968-04
- Volume
- 75
- Issue
- 4
- Pages
- 428
- ISSN
- 0002-9890 (ISSN-L)
- OpenAlex
- W2012140001
- Cited by
- 2,583
- References
- 0
- FWCI
- 20.05
- Type
- journal article
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.