Browse Prior Art Database

RECONSIDERING TURING'S THESIS (TOWARD MORE REALISTIC SEMANTICS OF PROGRAMS)

IP.com Disclosure Number: IPCOM000128484D
Original Publication Date: 1984-Sep-01
Included in the Prior Art Database: 2005-Sep-16
Document File: 9 page(s) / 37K

Publishing Venue

Software Patent Institute

Related People

Gurevich, Yuri: AUTHOR [+3]

Abstract

The classical computation model is based on the notion of a potentially infinite computing device (like a Turing machine or an idealized Pascal machine). We propose here an alternative computation model which explicitly recognizes finiteness of computers. The new operational semantics is especially appropriate in the case of algorithms sensitive to the bounds on machine resources (like algorithms for operating systems).

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 11% of the total text.

Page 1 of 9

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

THE UNIVERSITY OF MICHIGAN COMPUTING RESEARCH LABORATORY1

RECONSIDERING TURING'S THESIS (TOWARD MORE REALISTIC SEMANTICS OF PROGRAMS)

Yuri Gurevich

CRL-TR-36-84

September 1984

Room 1079, East Engineering Building
Ann Arbor, Michigan 48109
USA
Tel: (313) 763-8000

Reconsidering Turing s thesis (Toward more realistic semantics of programs) [ title ]

Yuri Gurevich 2 Department of Electrical Engineering and Computer Science The University of Michigan, Ann Arbor, MI 48109

Abstract.

The classical computation model is based on the notion of a potentially infinite computing device (like a Turing machine or an idealized Pascal machine). We propose here an alternative computation model which explicitly recognizes finiteness of computers. The new operational semantics is especially appropriate in the case of algorithms sensitive to the bounds on machine resources (like algorithms for operating systems).

Introduction

In the classical computation model algorithms are closely related to potentially infinite computing devices (like Turing machines or idealized Pascal machines). These devices interleave computing with extending the necessary resources in a manner reminiscent of human computing with pen and paper. In S1 we explain our reservations with respect to the claim --

1 Any opinions, findings, and conclusions or recommendations expressed in this publication are those of the authors and do not necessarily reflect the views of the funding agency.

2 Supported in part by NSF grant MCS83-01022

University of Michigan Computing Research Laboratory Page 1 Sep 01, 1984

Page 2 of 9

RECONSIDERING TURING'S THESIS (TOWARD MORE REALISTIC SEMANTICS OF PROGRAMS)

implicit in Turing's thesis -- that every Turing machine realises an algorithm. The same reservations apply to potentially infinite devices in general.

Our alternative to the notion of a potentially infinite machine is presented in S2. It is the notion of a uniform family of finite machines. This notion is to remain informal (like the notion of a potentially infinite machine in the classical case). A program for a uniform family of finite machines defines a global algorithm; every machine in the family executes a local version of the global algorithm. In particular, a program for a potentially infinite machine M defines a global algorithm for the family of finite versions of M; this global algorithm is insensitive to those resource bounds of the finite machines which vary from one machine to another. In S3 we discuss global algorithms which are sensitive to the bounds on varied resources. Such resource sensitive algorithms are most common in real world computing. Algorithms realized by operating systems obviously are resourse sensitive. But also many algorithms whose input-output relation is external to computers are resource sensitive for the sake of efficiency. An algorithm for sorting a large database, for example, may start with lo...