Please use this identifier to cite or link to this item: http://scholarbank.nus.edu.sg/handle/10635/36143
Title: Turing Machines and Automatic Functions as Models of Computation
Authors: SEAH CHENG'EN SAMUEL
Keywords: Turing Machines, Automatic Function, Computation Models
Issue Date: 25-Jul-2012
Source: 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.
URI: http://scholarbank.nus.edu.sg/handle/10635/36143
Appears in Collections:Master's Theses (Open)

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

OPEN

NoneView/Download

Page view(s)

167
checked on Dec 2, 2017

Download(s)

165
checked on Dec 2, 2017

Google ScholarTM

Check


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