Deck 11: Models of Computation

Question 1

The equation for the distance d that a moving vehicle travels - the product of rate r and time t - is considered to be a model.

Answer 1

True

Question 2

What can be done by an algorithm cannot be done by a Turing machine.

Answer 2

False

Question 3

Bit inversion is an algorithm that a Turing machine can process.

Answer 3

True

Question 4

A Turing machine cannot produce output.

Question 5

Each time a Turing machine operation is done, three actions take place.

Question 6

A Turing machine can store information in and retrieve it from memory.

Question 7

A computing agent must be able to act in accordance with algorithm instructions.

Question 8

There is a limit to the amount of memory available on a Turing machine.

Question 9

The Turing machine must execute instructions in the order that the instructions are numbered.

Question 10

The model of a phenomenon must capture the full functionality of the real thing.

Question 11

A Turing machine includes a tape that extends infinitely in both directions.

Question 12

A Turing machine always contains a special symbol to represent "blank".

Question 13

Each Turing machine instruction describes an operation that is unambiguous, requiring no additional explanation, and any Turing machine is able to carry out the operation described.

Question 14

The Turing machine is designed to carry out two types of primitive operations.

Question 15

In unary representation, any unsigned whole number n will be encoded by a sequence of n + 1 1s.

Question 16

You can think of a Turing machine as having an internal clock. Each tick of the clock performs a sequence of instructions.

Question 17

In any collection of Turing machine instructions, there can be two different instructions that both begin with the same current state and current symbol.

Question 18

A formal basis for mathematical proofs guarantees the presence of intuitive statements.

Question 19

Although we can compare two Turing machine algorithms for the same task, we cannot really compare the efficiency of a Turing machine algorithm that will be run on a "real" computer.

Question 20

The Turing machine contains two separate units that read one cell of the tape at a time and writes a symbol in that cell.

Question 21

At any point in time, only a finite number of cells in the Turing machine input contain ____ symbols.

A) blank
B) placeholder
C) alphabetic
D) nonblank

Question 22

The ____ thesis can never be proved because the definition of an algorithm is descriptive, not mathematical.

A) Church-Zimmerman
B) Church-Turing
C) Church-Alan
D) Alan-Zimmerman

Question 23

In a state diagram, ____ represent transitions from one state to another.

A) rectangles
B) circles
C) triangles
D) arrows

Question 24

A distinction must be made between a Turing machine as a computing agent and the algorithm it carries out.

Question 25

A(n) ____ is a statement advanced for consideration and maintained by argument.

A) algorithm
B) contradiction
C) thesis
D) 5-tuple

Question 26

The real value of Turing machines as models of computability is in exposing problems that are uncomputable.

Question 27

The term unary means that we will use ____ symbol(s).

A) 1
B) 2
C) 3
D) 4

Question 28

One consequence of an unsolvable problem related to the halting problem is that no program can be written to decide whether any given program always stops eventually, no matter what the input.

Question 29

The bit inverter Turing machine should have only one state.

Question 30

In a state diagram, ____are used to represent states.

A) arrows
B) circles
C) rectangles
D) triangles

Question 31

An extra bit, called a(n) ____, can be attached to the end of a string of bits.

A) state diagram
B) odd parity bit
C) algorithm
D) sentinel

Question 32

A tape is used to hold the ____ to the Turing machine.

A) alphabet
B) input
C) output
D) halting state

Question 33

Unsolvable problems related to the halting problem have the following practical consequence:

A) a program can be written to decide whether any given program run on any given input will produce some specific output
B) a program can be written to decide whether any two programs are equivalent
C) a program can be written to decide whether any given program always stops eventually, no matter what the input
D) no program can be written to decide whether any given program run on any given input will ever produce some specific output

Question 34

The ____ is the finite set of symbols that the Turing machine understands.

A) alphabet
B) placeholder
C) blank
D) palette

Question 35

The ____ states that if there exists an algorithm to do a symbol manipulation task, then there exists a Turing machine to do that task.

A) Church-Turing thesis
B) Church-Alan theorem
C) Church-Zimmerman thesis
D) Alan-Zimmerman thesis

Question 36

If a Turing machine program consists of the following four instructions:
(1,0,1,2,R)
(1,1,0,2,R)
(2,0,0,2,R)
(2,b,b,2,L)
Then which of the following is a halting configuration?

A) ... b 1 1 b b b ... (current state = 2, symbol 1 is being read)
B) ... b 1 1 b b b ... (current state = 1, symbol 1 is being read)
C) ... b 1 0 b b b ... (current state = 1, symbol 0 is being read)
D) ... b 1 0 b b b ... (current state = 2, symbol 0 is being read)

Question 37

Which of the following statements about the halting problem is correct?

A) it is a computable problem
B) no Turing machine exists to solve this problem
C) a Turing machine exists that solves the problem
D) if it cannot be done by a Turing machine, it is still computable

Question 38

The Turing machine captures all of the properties that are essential for a computing agent.

Question 39

Which of the following statements is correct?

A) scientists still think it is necessary to write a Turing machine when they talk about an algorithmic computation
B) a Turing machine that is executing an algorithm to solve some task must halt when begun on a tape containing input appropriate to that task
C) a Turing machine that is executing an algorithm to solve some task need not halt when begun on a tape containing input appropriate to that task
D) just running the Turing machine enables us to decide about halting

Question 40

A(n) ____ is a visual representation of a Turing machine algorithm.

A) parity bit
B) model
C) state diagram
D) incrementer

Question 41

State ____ is always the start-up state of the Turing machine.

A) 0
B) 1
C) L
D) R

Question 42

The job of a ____ is to change 0s to 1s and 1s to 0s.

A) bit inverter
B) parity bit machine
C) unary adder
D) Turing machine

Question 43

The proof by ____ approach assumes that a conclusion is true and shows that the assumption leads to an impossible situation.

A) contradiction
B) inference
C) deduction
D) impossibility

Question 44

A Turing machine ____ is a collection of instructions that allow a Turing machine to carry out a certain task.

A) program
B) sequence
C) algorithm
D) tape

Question 45

Turing machines define the limits of ____, which is what can be done by symbol manipulation algorithms.

A) computability
B) solubility
C) compatibility
D) correspondence

Question 46

A(n) ____ adds 1 to any number.

A) unary operator
B) bit adder
C) parity machine
D) incrementer

Question 47

Consider the Turing machine instruction shorthand notation, (current state, current symbol, next symbol, next state, X)
What does X represent?

A) direction of move
B) output
C) input
D) placeholder

Question 48

____ are used to detect errors that occur as a result of electronic interference when transmitting strings.

A) Parity bits
B) Unary operators
C) Bit inverters
D) Debuggers

Question 49

A formal basis for proofs allows for ____ theorem-proving.

A) unsolvable
B) mechanical
C) indisputable
D) observable

Question 50

The ____ deals with deciding if a collection of Turing machine instructions will ever halt.

A) Turing problem
B) parity problem
C) halting problem
D) incomputable problem