Chapter 1

Chapter 1

Chapter 10 OTHER MODELS OF TURING MACHINES Learning Objectives At the conclusion of the chapter, the student will be able to: Explain the concept of equivalence between classes of automata Describe how a Turing machine with a stay-option can be simulated by a

standard Turing machine Describe how a standard Turing machine can be simulated by a machine with a semi-infinite tape Describe how off-line and multidimensional Turing machines can be simulated by standard Turing machines Construct two-tape Turing machines to accept simple languages Describe the operation of nondeterministic Turing machines and their relationship to deterministic Turing machines Describe the components of a universal Turing machine Describe the operation of linear bounded automata and their relationship to standard Turing machines

Equivalence of Classes of Automata Two automata are equivalent if they accept the same language Given two classes of automata C1 and C2, if for every automaton in C1 there is an equivalent automaton in C2, the class C2 is at least as powerful as C1 If the class C1 is at least as powerful as C2, and the converse also holds, then the classes C1 and C2 are

equivalent Equivalence can be established either through a constructive proof or by simulation Turing Machines with a Stay-Option In a Turing Machine with a Stay-Option, the read-write head has the option to say in place after rewriting the cell content Theorem 10.1 states the class of Turing machines with a stay-option is equivalent to the class of standard Turing

machines To show equivalence, we argue that any machine with a stay-option can be simulated by a standard Turing machine, since the stay-option can be accomplished by A rule that rewrites the symbol and moves right, and A rule that leaves the tape unchanged and moves left Turing Machines with Semi-Infinite Tape As shown in Figure 10.2, a common variation of the

standard Turing machine is one in which the tape is unbounded only in one direction A Turing machine with semi-infinite tape is otherwise identical to the standard model, except that no left move is possible when the read-write head is at the tape boundary Equivalence of Standard Turing Machines and Semi-Infinite Tape Machines The classes are equivalent because, as shown in Figure 10.4,

any standard Turing machine can be simulated by a machine with a semi-infinite tape The simulating machine has two tracks: the upper track contains the symbols to the right of an arbitrary reference point, while the lower track contains those to the left of the reference point in reverse order The Off-Line Turing Machine As shown in Figure 10.6, an off-line Turing machine has a read-only input file in addition to the read-write tape Transitions are determined by both the current input

symbol and the current tape symbol Equivalence of Standard Turing Machines and Off-Line Turing Machines The classes are equivalent because, as shown in Figure 10.7, a standard Turing machine with four tracks can simulate the computation of an off-line machine Two tracks are used to store the input file contents and current position, while the other two tracks store the contents and current position of the read-write tape

Multitape Turing Machines As shown in Figure 10.8, a multitape Turing machine has several tapes, each with its own independent read-write head A sample transition rule for a two-tape machine must consider the current symbols on both tapes: (qq0, a, e) = (qq1, x, y, L, R) Equivalence of Standard Turing Machines and Multitape Turing Machines The classes are equivalent because, as shown in Figure 10.11,

a standard Turing machine with four tracks can simulate the computation of an off-line machine Two tracks are used to store the contents and current position of tape 1, while the other two tracks store the contents and current position of tape 2 Multidimensional Turing Machines As shown in Figure 10.12, a multidimensional Turing machine has a tape that can extend infinitely in more than one dimension In the case of a two-dimensional machine, the transition

function must specify movement along both dimensions Equivalence of Standard Turing Machines and Multidimensional Turing Machines The classes are equivalent because, as shown in Figure 10.13, a standard Turing machine with two tracks can simulate the computation of a two-dimensional machine In the simulating machine, one track is used to store the cell contents and the other one to keep the associated address

Nondeterministic Turing Machines A nondeterministic Turing machine is one with potentially many transition choices for a given (q state, symbol ) combination Example 10.2 presents a sample transition rule for a nondeterministic machine: (qq0, a) = {(qq1, b, R), (qq2, c, L)} Since multiple transitions may be applied at each step, the machine may have multiple active simultaneous threads, any of which may accept the input string when the thread halts

For every nondeterministic Turing machine, there is an equivalent deterministic machine that can simulate its operation A Universal Turing Machine A universal Turing machine is a reprogrammable Turing machine which, given as input the description of a Turing machine M and a string w, can simulate the computation of M on w A universal Turing machine has the structure of a multitape machine, as shown in Figure 10.16

Linear Bounded Automata The power of a standard Turing machine can be restricted by limiting the area of the tape that can be used A linear bounded automaton is a Turing machine that restricts the usable part of the tape to exactly the cells used by the input Input can be considered as bracketed by two special symbols or markers which can be neither overwritten nor skipped by the read-write head Linear bounded automata are assumed to be nondeterministic and accept languages in the same

manner as other Turing machine accepters Languages Accepted by Linear Bounded Automata It can be shown that any context-free language can be accepted by a linear bounded automaton In addition, linear bounded automata can be designed to accept languages which are not contextfree, such as L = { anbncn: n 1 } While it is difficult to come up with a concrete and explicitly defined language to use as an example,

linear bounded automata are not as powerful as standard Turing machines

Recently Viewed Presentations

  • Legislative update

    Legislative update

    HB 41 - Extend the Cultural Integrity and Commitment Act. Bill Overview: HB 41 extends the Indian language immersion program including funding for school districts and extends the Cultural Integrity and Commitment Act passed with SB 272 (2015), adjusting the...
  • The Nordic Microsystem Manufacturing Cluster

    The Nordic Microsystem Manufacturing Cluster

    The following MPW services are offered through Europractice: Bulk Micromachining MPW MultiMEMS (SensoNor) Surface Micromachining MPW Bosch SOI Micromachining MPW MEMSOI (TRONIC'S Microsystems) MPW for diffractive optical elements CSEM Foundry processes in MultiMEMS Based on SensoNor's 4th generation wafer process...
  • CSC 405 Introduction to Computer Security

    CSC 405 Introduction to Computer Security

    CSC 405 Introduction to Computer Security Topic 5. Trusted Operating Systems -- Part I Secure v.s. Trusted Secure Something either is or is not secure Property of presenter Asserted based on product characteristics Absolute: not qualified as to how, where,...
  • Simulation and impact study of future spaceborne Doppler wind ...

    Simulation and impact study of future spaceborne Doppler wind ...

    Evaluation of potential impacts of future Japan's space-based Doppler Wind Lidar (DWL) on polar- and tropical-orbiting satellite in Japan. Kozo Okamoto1,2
  • Chapter 20 Introduction to macroeconomics

    Chapter 20 Introduction to macroeconomics

    Some key issues in macroeconomics Inflation the rate of change of the general price level Unemployment a measure of the number of people looking for work, but who are without jobs Output real gross national product (GNP) measures total income...
  • Mass Flowers - Katy ISD

    Mass Flowers - Katy ISD

    Very wide range of colors Name is from the Latin word rana (frog) referring to the fact that many wild roses grow in wet areas Tulip Red, pink, white, yellow, orange, purple and bi-colors Availability: November through May, limited availability...
  • You need: Feb.20, 2019 Clean paper / pencil

    You need: Feb.20, 2019 Clean paper / pencil

    Arial Comic Sans MS Wingdings Ripple 1_Ripple Feb.20, 2019 PowerPoint Presentation Mental Math checking Today's checklist: Any order, but be careful - textbook is here and web sites can be reached from home. MRS. NERG-C Cells How are we able...
  • Lab: Cells - Wilson's Website

    Lab: Cells - Wilson's Website

    Slide 8 Cheek Cells - Low Power Slide 9 Cheek Cells - High Power Slide 10 -Purpose of Iodine: Outlines the big parts of the cell such as the Nucleus and Plasma membrane. Slide 11 Elodea Cell - Low Power...