Question 1

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.

Accepted Answer

A) True 
 B)False

Question 2

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

Accepted Answer

A)   unsolvable
B)   mechanical
C)   indisputable
D)   observableE) All of the above
F) C) and D)

Question 3

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

Accepted Answer

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 computableE) B) and D)
F) A) and B)

Question 4

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 outputE) A) and B)
F) C) and D)

Question 5

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

Accepted Answer

A) True 
 B)False

Question 6

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

Accepted Answer

A)   Turing problem
B)   parity problem
C)   halting problem
D)   incomputable problemE) A) and C)
F) B) and C)

Question 7

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

Accepted Answer

A)   algorithm
B)   contradiction
C)   thesis
D)   5-tupleE) All of the above
F) C) and D)

Question 8

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

Accepted Answer

A) True 
 B)False

Question 9

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

Accepted Answer

A)   state diagram
B)   odd parity bit
C)   algorithm
D)   sentinelE) C) and D)
F) B) and C)

Question 10

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.

Accepted Answer

A) True 
 B)False

Exam 11: Models of Computation

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

Correct Answer
verified

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.

Correct Answer
verified

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

Correct Answer
verified

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

Correct Answer
verified

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

Correct Answer
verified

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.

Correct Answer
verified

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

Correct Answer
verified

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

Correct Answer
verified

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

Correct Answer
verified

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

Correct Answer
verified

Exam 11: Models of Computation

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

Correct AnswerverifiedShow Answer

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.

Correct AnswerverifiedShow Answer

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

Correct AnswerverifiedShow Answer

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

Correct AnswerverifiedShow Answer

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

Correct AnswerverifiedShow Answer

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.

Correct AnswerverifiedShow Answer

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

Correct AnswerverifiedShow Answer

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

Correct AnswerverifiedShow Answer

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

Correct AnswerverifiedShow Answer

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

Correct AnswerverifiedShow Answer

Correct Answer
verified

Correct Answer
verified

Correct Answer
verified

Correct Answer
verified

Correct Answer
verified

Correct Answer
verified

Correct Answer
verified

Correct Answer
verified

Correct Answer
verified

Correct Answer
verified