FiltersDone

Question type

Essay

Multiple Choice

Short Answer

True False

Matching

Exam 12: Models of Computation

Show Answer

Share

---

All types

Filters

Study Flashcards

Question 21

True/False

Review LaterAdd Note

Review Later

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

A) True
B) False

Correct Answer

verified

Show Answer

Question 22

Multiple Choice

Review LaterAdd Note

Review Later

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

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

E) All of the above
F) None of the above

Correct Answer

verified

Show Answer

Question 23

True/False

Review LaterAdd Note

Although we can compare two Turing machine algorithms for the same task, we can't really compare the efficiency of a Turing machine algorithm with an algorithm that runs on a "real" computer.

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

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

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

A Turing machine cannot produce output.

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

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

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

In a state diagram, ____ are used to represent states.

Explain how a Turing machine differs in scale from any real computing agent.

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

A Turing machine includes a(n) tape that extends infinitely in both directions._________________________

List three practical consequences arising from unsolvable programs related to the halting problem.

Discuss at length the assertion that Turing machines define the limits of computability.

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

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

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

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