Please use this identifier to cite or link to this item:
Title: Turing Machines and Automatic Functions as Models of Computation
Keywords: Turing Machines, Automatic Function, Computation Models
Issue Date: 25-Jul-2012
Citation: SEAH CHENG'EN SAMUEL (2012-07-25). Turing Machines and Automatic Functions as Models of Computation. ScholarBank@NUS Repository.
Abstract: In the present report it is shown that a function is automatic if and only if a one-tape Turing machine can compute it in linear time where input and output have to start at the left end of the tape. It is also shown that the same equivalence holds when non-deterministic one-tape Turing machines are considered. This result is extended to the study of the complexity class AF[log n] which is roughly the class of functions which can be computed by a machine with automatic functions as primitive operations in logarithmic time. It is shown that AF[log n] is a proper subclass of DTIME[n log n] but still significantly larger than the class AF[1] of automatic functions.
Appears in Collections:Master's Theses (Open)

Show full item record
Files in This Item:
File Description SizeFormatAccess SettingsVersion 
SeahCES.pdf1.66 MBAdobe PDF



Page view(s)

checked on Nov 24, 2018


checked on Nov 24, 2018

Google ScholarTM


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.