panel

The Turing Computational Model

Authors:

Andrew C. YaoAuthors Info & Claims

ACM-TURING '12: ACM Turing Centenary Celebration

Article No.: 8, Page 1

https://doi.org/10.1145/2322176.2322184

Published: 15 June 2012 Publication History

Abstract

The panel presentations will discuss the beauty and simplicity of the Turing machine formulation of the previously elusive concept of computability and the intuitively satisfying explanation of the power and limitations of computability. They will also review how the Turing machine model provided simple proofs of deep results in logic, including Gödel’s incompleteness theorem. The panel will also examine specifi c results in computer science infl uenced by the Turing machine model as well as how it shaped the development of computational complexity theory. Quantum computing will be discussed and its relationship to the classic Turing machine model. The panel will also discuss what Alan Turing might say about the Inevitable Fallibility of Software.

Supplementary Material

JPG File (06-fri-acm.jpg)

Download
20.94 KB

MP4 File (06-fri-acm.mp4)

Download
356.40 MB

Recommendations

Turing the Man
ACM-TURING '12: ACM Turing Centenary Celebration

The panelists will discuss Alan Turing and Sara Turing, his mother, based on the personal experiences of the panelists. William newman will recount amusing incidents during the time Turing was a regular visitor at the newman home. Kelly gotlieb will ...
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-...
Alan Turing and Bletchley Park

This month marks the 100th anniversary of Alan Turing's birth. His ground-breaking work in the 1940s continues to have animpact on computer science as we know it. The first featured Web extra at http://youtu.be/5nK_ft0Lf1s is a video interview with Paul ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

ACM-TURING '12: ACM Turing Centenary Celebration

June 2012

35 pages

ISBN:9781450339193

DOI:10.1145/2322176

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 15 June 2012

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Panel

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

0
Total Citations
243
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 12 Dec 2024

Other Metrics

View Author Metrics

Citations

View Options

View options

Login options

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

Abstract

Supplementary Material

Recommendations

Turing the Man

Some properties of one-pebble turing machines with sublogarithmic space

Alan Turing and Bletchley Park

Comments

Information

Published In

Publisher

Publication History

Permissions

Check for updates

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

View options

Login options

Full Access

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations