Deck 12: Models of Computation

Question 1

The Turing machine contains two separate units, one for input and one for output.

Answer 1

False

Question 2

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

Answer 2

uncomputable

Question 3

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 3

True

Question 4

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

Question 5

Every problem has an algorithmic solution.

Question 6

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

Question 7

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 8

Prototypes are an important way of studying many physical and social phenomena. _________________________

Question 9

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

Question 10

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

Question 11

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.

Question 12

The bit inverter Turing machine should have two states. _________________________

Question 13

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

Question 14

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

Question 15

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

Question 16

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

Question 17

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

Question 18

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.

Question 19

Models can only give us information about existing phenomena.

Question 20

A Turing machine cannot produce output.

Question 21

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

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

Question 22

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

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

Question 23

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

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

Question 24

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

Question 25

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

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

Question 26

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 27

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

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

Question 28

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 29

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 30

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

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

Question 31

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

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

Question 32

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 33

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

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

Question 34

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

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

Question 35

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

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

Question 36

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

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

Question 37

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 38

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

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

Question 39

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

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

Question 40

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

A) state bit
B) odd parity bit
C) inverted bit
D) sentinel bit

Question 41

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

Question 42

Discuss the ways in which a Turing machine does or does not satisfy the requirement that an algorithm be a well-ordered collection.

Question 43

Describe in detail what a Turing machine includes.

Question 44

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?

Question 45

According to its definition, what must an algorithm be or do?

Question 46

Given that we can make a comparison between two Turing machine algorithms for the same task, can we compare the efficiency of a Turing machine algorithm with one that runs on a "real" computer?

Question 47

What do we require any computing agent to be able to do?

Question 48

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

Question 49

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