Dean, Walter (2016) Squeezing feasibility. In: 12th Conference on Computability in Europe, CiE 2016 : Pursuit of the Universal, Paris, France, 27 Jun - 1 Jul 2016. Published in: Pursuit of the Universal. CiE 2016. , 9709 pp. 78-88. ISSN 0302-9743. doi:10.1007/978-3-319-40189-8_8

Research output not available from this repository, contact author.

Request Changes to record.

Abstract

This note explores an often overlooked question about the characterization of the notion model of computation which was originally identified by Cobham [5]. A simple formulation is as follows: what primitive operations are allowable in the definition of a model such that its time and space complexity measures provide accurate gauges of practical computational difficulty? After exploring the significance of this question in the context of subsequent work on machine models and simulations, an adaptation of Kreisel’s squeezing argument [17] for Church’s Thesis involving Gandy machines [11] is sketched which potentially bears on this question.

Item Type:	Conference Item (Paper)
Subjects:	Q Science > QA Mathematics > QA75 (Please use QA76 Electronic Computers. Computer Science)
Divisions:	Faculty of Social Sciences > Philosophy
Series Name:	Lecture notes in computer science
Journal or Publication Title:	Pursuit of the Universal. CiE 2016.
Publisher:	Springer
ISSN:	0302-9743
Official Date:	14 June 2016
Dates:	Date Event 14 June 2016 Published
Volume:	9709
Page Range:	pp. 78-88
DOI:	10.1007/978-3-319-40189-8_8
Status:	Peer Reviewed
Publication Status:	Published
Access rights to Published version:	Restricted or Subscription Access
Conference Paper Type:	Paper
Title of Event:	12th Conference on Computability in Europe, CiE 2016 : Pursuit of the Universal
Type of Event:	Conference
Location of Event:	Paris, France
Date(s) of Event:	27 Jun - 1 Jul 2016
Related URLs:	Organisation

Request changes or add full text files to a record

Repository staff actions (login required)

View Item