Lakehead University Library Logo
    • Login
    View Item 
    •   Knowledge Commons
    • Electronic Theses and Dissertations
    • Retrospective theses
    • View Item
    •   Knowledge Commons
    • Electronic Theses and Dissertations
    • Retrospective theses
    • View Item
    JavaScript is disabled for your browser. Some features of this site may not work without it.
    quick search

    Browse

    All of Knowledge CommonsCommunities & CollectionsBy Issue DateAuthorTitleSubjectDisciplineAdvisorCommittee MemberThis CollectionBy Issue DateAuthorTitleSubjectDisciplineAdvisorCommittee Member

    My Account

    Login

    Statistics

    View Usage Statistics

    Computation using s-programs

    Thumbnail

    View/Open

    WenY1987m-1b.pdf (5.209Mb)

    Date

    1987

    Author

    Wen, Yandan

    Degree

    Master of Science

    Discipline

    Mathematical Sciences

    Subject

    Machine theory
    Formal languages

    Metadata

    Show full item record

    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.

    URI

    http://knowledgecommons.lakeheadu.ca/handle/2453/917

    Collections

    • Retrospective theses

    Lakehead University Library
    Contact Us | Send Feedback

     


    Lakehead University Library
    Contact Us | Send Feedback