Test #4 Review Flashcards
Turing machines have a built in stack
false
a transition of a turing machine may perform which of the following? Select all that apply
writes a symbol onto tape
moves one cell to right
moves one cell to left
a turing machine consists of which of the following? select all that apply
a finite control unit
an input tape
a head positioned on the tape
Every turing machine has an initial state which is the state in which the turing machine starts
true
The input tape of a turing machine has a right border and can be extended indefinitely to the left
False
The Church-Turing thesis states that every computer algorithm can be implemented as a push-down automata.
False
The next state of a Turing machine is determined by its current state and the character under the read/write head.
True
A Turning machine has a set H of special states called halting states where, if the machine enters one of these states, it halts immediately.
True
Alan Turing proved that there is a Turing machine that solves the Halting Problem
False
The Halting Problem considers whether, for an arbitrary computer program and an input to that program, the program will halt or continue to run forever.
True
The use of multiple input tapes makes the basic Turing machine more powerful.
False
The use of multiple read/write heads makes the basic turning machine more powerful
False
Which of the following statements are True about a Turing machine with multiple input tapes. Select all that apply.
There is one read/write head for each input tape
At each step, the Turing machine scans the symbols observed by all the heads
There is one read/write head for each input tape
At each step, the Turing machine scans the symbols observed by all the heads
The Turing Machine R⊔ moves right until it finds the first blank character in the input string. If the read/write head is already on a blank, then it stays there without moving.
True
There is a Turing Machine that can add 1 to a binary number.
True
Determining whether, given a Turing machine and a specific input, the Turing machine will finish running (halt) or continue to run forever (stuck), is referred to as the Halting Problem.
True
There is a Turing machine that solves the Halting Problem
False
A Turing Machine is no more powerful than a push-down automata.
False
The only way for a Turning Machine to “remember” a specific input character is to represent that character with a special “state”
True
The Turing machine in Figure #2 does what? Assume the string: abaa with starting state on left-most a.
Transforms the string w into w followed by a blank followed by another copy of w
The Turing machine in Figure #3 does what? Select the best answer.
Suppose to memorize a nonblank character “a”, move to the left one cell, and write “a” over whatever character happens to be in that cell, but there is an error in the code.
The Turing machine in Figure #4 does what?
Move right until you reach the first non-blank character
What does the Turing machine in Figure #5 do?
Adds 1 to the binary number
The first thing the Turing machine in Figure #6 does is to mark the end of string with a “1” and then move to the rightmost character “a”
True
The second thing the turning machine in Figure #6 does is to replace the rightmost “a” with a blank and then move to the rightmost “b” and replace it with a blank.
False
The Turning machine in Figure #6 places a “1” on the input tape in the left-most position and places blanks everywhere else if the input string is the correct format.
True
What does the Turing Machine in Figure #7 do?
Computes the lower-case equivalent of the input string
What does the Turing Machine in Figure #8 do?
Accepts strings that contain 101
The Turing machine in Figure #9 resolves the language L = wwR
True
For the input string: abaaaabb, the Turnig Machine in Figure 9 erases the string and places a “1” on the input tape
False
The Turing Machine R⊔ moves right until it finds the first blank character in the input string. If the read/write head is already on a blank, then it stays there without moving.
True
The first stage (q0-q3) of the Turing Machine in Figure #10 converts each “1” to “x” and each “0” to “y”, and finds the midpoint of the string
False
The second stage (q4) of the Turing Machine in figure #10 converts each “x” and “y” in first half of string back to “0” and “1”
True
The third stage (q5-q8 and qf) of the Turing Machine in Figure #10 converts each symbol on the left half of the string to “x” or “y” and all symbols on the right part of the string to blanks (if the initial string is in the form: ww).
True
