Deck 12: Models of Computation

Question 1

A Turing machine includes a(n)infinite platter that can be stamped with only one symbol per sector. _________________________

Answer 1

False

Question 2

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

Answer 2

False

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

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 5

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

Question 6

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

Question 7

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.

Question 8

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

Question 9

A Turing machine can produce output on the same tape upon which the input exists.

Question 10

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

Question 11

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

Question 12

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

Question 13

The bit inverter Turing machine should have two states . _________________________

Question 14

The model of a phenomenon does not need to capture the full functionality of the real thing.

Question 15

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

Question 16

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

Question 17

Every problem has an algorithmic solution.

Question 18

Models can only give us information about existing phenomena.

Question 19

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

Question 20

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

Question 21

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 22

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

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

Question 23

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 24

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

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

Question 25

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 26

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 27

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 28

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 29

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

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

Question 30

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

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

Question 31

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 the configuration ____ 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 32

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 33

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

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

Question 34

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

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

Question 35

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 36

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 37

A(n)____ takes the bits in a string and changes the 1s to 0s and the 0s to 1s.

A)bit inverter
B)unary converter
C)Turing inverter
D)incrementer

Question 38

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 39

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 40

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 41

Discuss some real world uses for a bit inverter.

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

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

Question 45

Why cannot we compare algorithms running on Turing machines to the same algorithms running on "real" computers?

Question 46

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

Question 47

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 48

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

Question 49

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

Question 50

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