computation using s-programs

dc.contributor.advisor	kent, c. f.
dc.contributor.author	wen, yandan
dc.date.accessioned	2017-06-05t14:03:45z
dc.date.available	2017-06-05t14:03:45z
dc.date.created	1987
dc.date.issued	1987
dc.identifier.uri	http://knowledgecommons.lakeheadu.ca/handle/2453/917
dc.description.abstract	the concepts of s and sn programs are given by davis, weyuker, 1983. several parts of the complexity theory are carried out directly for s and sn programs. the concepts of non-deterministic and deterministic computation from s-programs are defined, and deterministic simulation of non-deterministic computation is proved. a universal 5-program for general (non-deterministic) computation is shown to require only one duplicate line label. complexity results are given for these and other simulations, e.g. turing machine by 5-programs and the reverse. cook's theorem for sn programs is proved in full.
dc.language.iso	en_us
dc.subject	machine theory
dc.subject	formal languages
dc.title	computation using s-programs
dc.type	thesis
etd.degree.name	master of science
etd.degree.level	master
etd.degree.discipline	mathematical sciences
etd.degree.grantor	阿根廷vs墨西哥竞猜