Question 1

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

Accepted Answer

uncomputable

Question 2

It is important to note that unsolvable problems related to the halting problem are unsolvable because of their ____.

Accepted Answer

A)  generality
B)  complexity
C)  specificity
D)  simplicity A

Question 3

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

Accepted Answer

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. D

Question 4

The proof by ____ approach assumes that a specific Turing machine does exist and then shows that this assumption leads to an impossible situation.

Accepted Answer

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

Question 5

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

Accepted Answer

A)  one
B)  two
C)  three
D)  four

Question 6

The Turing machine contains a single unit for both input and output.

Accepted Answer

A) True 
 B)False

Question 7

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

Accepted Answer

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

Question 8

What are four characteristics of the model of a physical or social phenomenon?

Accepted Answer

The answer of What are four characteristics of the model...

Question 9

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.

Accepted Answer

A) True 
 B)False

Question 10

If we post a program and try to construct a Turing machine to solve it but are not successful, does this prove that no Turing machine exists? If not, why would prove this?

Accepted Answer

The answer of If we post a program and try...

Question 11

We assumed that there was a Turing machine that could solve the halting problem, and this assumption led to a(n)____.

Accepted Answer

A)  computable problem
B)  impossible situation
C)  unsolved problem
D)  complex solution

Question 12

In a _______ diagram, circles are used to represent states.

Accepted Answer

A)  state
B)  tape
C)  unary
D)  binary

Question 13

A formal basis for proofs might allow for ____ theorem-proving.

Accepted Answer

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

Question 14

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

Accepted Answer

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

Question 15

We can write a Turing machine to add 1 to any number; such a machine is often called a(n)____.

Accepted Answer

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

Question 16

One consequence of a(n)____________________ 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 is.

Accepted Answer

The answer of One consequence of a(n)____________________ problem related to...

Question 17

In binary representation, any unsigned whole number n is encoded by a sequence of n + 1 1s. _________________________

Accepted Answer

A) True 
 B)False

Question 18

It's possible to compare the efficiency of a Turing machine algorithm with an algorithm that runs on a "real" computer.

Accepted Answer

A) True 
 B)False

Question 19

In what ways are a Turing machine and an algorithm identical?

Accepted Answer

The answer of In what ways are a Turing machine...

Question 20

The symbols for a Turing machine must come from a finite set of symbols called the tape ____.

Accepted Answer

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

Exam 12: Models of Computation

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

It is important to note that unsolvable problems related to the halting problem are unsolvable because of their ____.

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

The proof by ____ approach assumes that a specific Turing machine does exist and then shows that this assumption leads to an impossible situation.

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

The Turing machine contains a single unit for both input and output.

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

What are four characteristics of the model of a physical or social phenomenon?

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.

If we post a program and try to construct a Turing machine to solve it but are not successful, does this prove that no Turing machine exists? If not, why would prove this?

We assumed that there was a Turing machine that could solve the halting problem, and this assumption led to a(n) ____.

In a _______ diagram, circles are used to represent states.

A formal basis for proofs might allow for ____ theorem-proving.

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

We can write a Turing machine to add 1 to any number; such a machine is often called a(n) ____.

One consequence of a(n)____________________ 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 is.

In binary representation, any unsigned whole number n is encoded by a sequence of n + 1 1s. _________________________

It's possible to compare the efficiency of a Turing machine algorithm with an algorithm that runs on a "real" computer.

In what ways are a Turing machine and an algorithm identical?

The symbols for a Turing machine must come from a finite set of symbols called the tape ____.