NDLI: Feedback Turing Computability, and Turing Computability as Feedback

Content Provider	IEEE Xplore Digital Library
Author	Ackerman, N.L. Freer, C.E. Lubarsky, R.S.
Copyright Year	2015
Description	Author affiliation: AI Lab., Massachusetts Inst. of Technol., Cambridge, MA, USA (Freer, C.E.) \|\| Dept. of Math., Harvard Univ., Cambridge, MA, USA (Ackerman, N.L.) \|\| Dept. of Math. Sci., Florida Atlantic Univ., Boca Raton, FL, USA (Lubarsky, R.S.)
Abstract	The notion of a feedback query is a natural generalization of choosing for an oracle the set of indices of halting computations. Notice that, in that setting, the computations being run are different from the computations in the oracle: the former can query an oracle, whereas the latter cannot. A feedback computation is one that can query an oracle, which itself contains the halting information about all feedback computations. Although this is self-referential, sense can be made of at least some such computations. This threatens, though, to obliterate the distinction between con- and divergence: before running a computation, a machine can ask the oracle whether that computation converges, and then run it if and only if the oracle says "yes." This would quickly lead to a diagonalization paradox, except that a new distinction is introduced, this time between freezing and non-freezing computations. The freezing computations are even more extreme than the divergent ones, in that they prevent the dovetailing on all computations into a single run. In this paper, we study feedback around Turing computability. In one direction, we examine feedback Turing machines, and show that they provide exactly hyper arithmetic computability. In the other direction, Turing computability is itself feedback primitive recursion (at least, one version thereof). We also examine parallel feedback. Several different notions of parallelism in this context are identified. We show that parallel feedback Turing machines are strictly stronger than sequential feedback TMs, while in contrast parallel feedback p.r. Is the same as sequential feedback p.r.
Starting Page	523
Ending Page	534
File Size	283534
Page Count	12
File Format	PDF
ISBN	9781479988754
ISSN	10436871
DOI	10.1109/LICS.2015.55
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2015-07-06
Publisher Place	Japan
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Turing machines Vegetation Indexes Standards Electronic mail Computational modeling Registers least fixed points Computability theory hyperarithmetic computability
Content Type	Text
Resource Type	Article
Subject	Mathematics Software

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Feedback Turing Computability, and Turing Computability as Feedback

On the Ordered Conjecture

Feedback Turing Computability, and Turing Computability as Feedback

Listings and Logics

Turing Machines with Atoms

Making turing machines accessible to blind students

Relational Temporal Machines

Coupling computations through space

Computability by Probabilistic Turing Machines

Feedback Turing Computability, and Turing Computability as Feedback

Similar Documents

Feedback Turing Computability, and Turing Computability as Feedback

On the Ordered Conjecture

Feedback Turing Computability, and Turing Computability as Feedback

Listings and Logics

Turing Machines with Atoms

Making turing machines accessible to blind students

Relational Temporal Machines

Coupling computations through space

Computability by Probabilistic Turing Machines

Feedback Turing Computability, and Turing Computability as Feedback