Deviant Encodings
Type of content
Oral Presentation
UC permalink
Publisher's DOI/URI
Thesis discipline
Degree name
Publisher
Journal Title
Journal ISSN
Volume Title
Language
Date
2003
Authors
Copeland, B. Jack
Proudfoot, D
Abstract
What is computation? We describe a number of related techniques that enable Turing machines to solve the halting problem. In each case, the machine’s (supposedly impossible) behaviour is made possible by a feature of the encoding scheme employed either to represent the input or to represent the output. Some means of excluding these deviant encodings is required when using the Turing-machine concept to define the traditional set of computable functions. The exercise of quarantining deviant encodings casts fresh light on Turing's historic definition of computability.
Description
Citation
Copeland BJ, Proudfoot D (2003). Deviant Encodings and the Turing Definition of Computability. La Trobe University, Melbourne, Australia, 2003.
Keywords
Ngā upoko tukutuku/Māori subject headings
ANZSRC fields of research
46 - Information and computing sciences::4613 - Theory of computation
Rights
All rights reserved unless otherwise stated