A Turing Machine for Exponential Function

Download Edit this record How to cite View on PhilPapers
Abstract
This is a Turing Machine which computes the exponential function f(x,y) = xˆy. Instructions format and operation of this machine are intended to best reflect the basic conditions outlined by Alan Turing in his On Computable Numbers, with an Application to the Entscheidungsproblem (1936), using the simplest single-tape and single-symbol version, in essence due to Kleene (1952) and Carnielli & Epstein (2008). This machine is composed by four basic task machines: one which checks if exponent y is zero, a second which checks if base x is zero, a third that is able to copy the base, and a fourth able to multiply multiple factors (in this case, factors will be all equal). They were conveniently separated in order to ease the reader's task to understand each step of its operation. We adopt the convention that a number n is represented by a string of n+1 symbols "1". Thus, an entry (x, y) will be represented by two respective strings of x+1 and y+1 symbols "1", separated by a single "0" (or a blank), and as an output, this machine will generate a string of (xˆy)+1 symbols "1". Some of the instructions are followed by a brief description of what's going on.
PhilPapers/Archive ID
LEMATM
Upload history
Archival date: 2013-01-03
View other versions
Added to PP index
2013-01-03

Total views
2,832 ( #1,063 of 64,138 )

Recent downloads (6 months)
166 ( #3,129 of 64,138 )

How can I increase my downloads?

Downloads since first upload
This graph includes both downloads from PhilArchive and clicks on external links on PhilPapers.