article

Free access

A Variant to Turing's Theory of Computing Machines

Author:

Hao WangAuthors Info & Claims

Journal of the ACM (JACM), Volume 4, Issue 1

Pages 63 - 92

https://doi.org/10.1145/320856.320867

Published: 01 January 1957 Publication History

PDF eReader

References

[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.

Crossref

Google Scholar

Cited By

View all

Kissner MBino LPäsler FCaruana PGhalanos G(2024)An All-Optical General-Purpose CPU and Optical Computer ArchitectureJournal of Lightwave Technology10.1109/JLT.2024.345845942:22(7999-8013)Online publication date: 15-Nov-2024
https://doi.org/10.1109/JLT.2024.3458459
Roberts J(2024)How Powerful are Decoder-Only Transformer Neural Models?2024 International Joint Conference on Neural Networks (IJCNN)10.1109/IJCNN60899.2024.10651286(1-8)Online publication date: 30-Jun-2024
https://doi.org/10.1109/IJCNN60899.2024.10651286
Morita K(2021)An instruction set for reversible Turing machinesActa Informatica10.1007/s00236-020-00388-158:4(377-396)Online publication date: 1-Aug-2021
https://dl.acm.org/doi/10.1007/s00236-020-00388-1
Show More Cited By

Index Terms

A Variant to Turing's Theory of Computing Machines
1. Theory of computation
  1. Models of computation
    1. Computability
      1. Turing 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
Abstract
It 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

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

Journal of the ACM Volume 4, Issue 1

Jan. 1957

92 pages

ISSN:0004-5411

EISSN:1557-735X

DOI:10.1145/320856

Issue’s Table of Contents

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 January 1957

Published in JACM Volume 4, Issue 1

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

120
Total Citations
View Citations
1,391
Total Downloads

Downloads (Last 12 months)186
Downloads (Last 6 weeks)19

Reflects downloads up to 01 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Kissner MBino LPäsler FCaruana PGhalanos G(2024)An All-Optical General-Purpose CPU and Optical Computer ArchitectureJournal of Lightwave Technology10.1109/JLT.2024.345845942:22(7999-8013)Online publication date: 15-Nov-2024
https://doi.org/10.1109/JLT.2024.3458459
Roberts J(2024)How Powerful are Decoder-Only Transformer Neural Models?2024 International Joint Conference on Neural Networks (IJCNN)10.1109/IJCNN60899.2024.10651286(1-8)Online publication date: 30-Jun-2024
https://doi.org/10.1109/IJCNN60899.2024.10651286
Morita K(2021)An instruction set for reversible Turing machinesActa Informatica10.1007/s00236-020-00388-158:4(377-396)Online publication date: 1-Aug-2021
https://dl.acm.org/doi/10.1007/s00236-020-00388-1
Fernau H(2021)Parsimonious Computational CompletenessDevelopments in Language Theory10.1007/978-3-030-81508-0_2(12-26)Online publication date: 16-Aug-2021
https://dl.acm.org/doi/10.1007/978-3-030-81508-0_2
Icard T(2020)Calibrating generative models: The probabilistic Chomsky–Schützenberger hierarchyJournal of Mathematical Psychology10.1016/j.jmp.2019.10230895(102308)Online publication date: Apr-2020
https://doi.org/10.1016/j.jmp.2019.102308
Sgantzos KGrigg I(2019)Artificial Intelligence Implementations on the Blockchain. Use Cases and Future ApplicationsFuture Internet10.3390/fi1108017011:8(170)Online publication date: 2-Aug-2019
https://doi.org/10.3390/fi11080170
Anisimov ANovokshonov A(2019)Verifiable Arithmetic Computations Using Additively Homomorphic Tags2019 IEEE International Conference on Advanced Trends in Information Theory (ATIT)10.1109/ATIT49449.2019.9030485(93-96)Online publication date: Dec-2019
https://doi.org/10.1109/ATIT49449.2019.9030485
Abbott R(2019)The Bit (and Three Other Abstractions) Define the Borderline Between Hardware and SoftwareMinds and Machines10.1007/s11023-018-9486-129:2(239-285)Online publication date: 1-Jun-2019
https://dl.acm.org/doi/10.1007/s11023-018-9486-1
Wright C(2019)A Proof of Turing Completeness in Bitcoin ScriptIntelligent Systems and Applications10.1007/978-3-030-29516-5_23(299-313)Online publication date: 24-Aug-2019
https://doi.org/10.1007/978-3-030-29516-5_23
De Mol LMaarten BDaylight E(2018)Less Is More in the Fifties: Encounters between Logical Minimalism and Computer Design during the 1950sIEEE Annals of the History of Computing10.1109/MAHC.2018.01217126540:1(19-45)Online publication date: Jan-2018
https://doi.org/10.1109/MAHC.2018.012171265
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

References

Cited By

Index Terms

Recommendations

Theory of one-tape linear-time Turing machines

Some properties of one-pebble turing machines with sublogarithmic space

Weight-reducing Turing machines

Comments

Information

Published In

Publisher

Publication History

Permissions

Check for updates

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

PDF

eReader

Login options

Full Access

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations