Deck 12: Models of Computation

Full screen (f)
exit full mode
Question
The model of a phenomenon must capture the full functionality of the real thing.
Use Space or
up arrow
down arrow
to flip the card.
Question
Prototypes are an important way of studying many physical and social phenomena._________________________
Question
There is no limit to the amount of ____________________ available on a Turing machine.
Question
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.
Question
Each time a Turing machine operation is done, four actions take place._________________________
Question
A formal basis for mathematical proofs guarantees the presence of intuitive statements.
Question
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
The Turing machine must execute instructions in the order that the instructions are numbered.
Question
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
In binary representation, any unsigned whole number n is encoded by a sequence of n + 1 1s._________________________
Question
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
A Turing machine cannot produce output.
Question
A Turing machine includes a(n) tape that extends infinitely in both directions._________________________
Question
Every problem has an algorithmic solution.
Question
The Turing machine contains two separate units, one for input and one for output.
Question
The bit inverter Turing machine should have two states._________________________
Question
The real value of Turing machines as models of computability is in exposing problems that are ____________________.
Question
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
Models can only give us information about existing phenomena.
Question
A computing agent must be able to act in accordance with ____________________ instructions.
Question
What are four characteristics of the model of a physical or social phenomenon?
Question
A tape is used to hold the ____ to the Turing machine.

A) alphabet
B) input
C) output
D) halting state
Question
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
A(n) ____ is a statement advanced for consideration and maintained by argument.

A) algorithm
B) contradiction
C) thesis
D) 5-tuple
Question
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
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
In a state diagram, ____ are used to represent states.

A) arrows
B) circles
C) rectangles
D) triangles
Question
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
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
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
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
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
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
A(n) ____ is a visual representation of a Turing machine algorithm.

A) parity bit
B) model
C) state diagram
D) incrementer
Question
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
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
State ____ is always the start-up state of the Turing machine.

A) 0
B) 1
C) L
D) R
Question
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
The term unary means that we will use ____ symbol(s).

A) one
B) two
C) three
D) four
Question
A formal basis for proofs might allow for ____ theorem-proving.

A) unsolvable
B) mechanical
C) indisputable
D) observable
Question
Explain how a Turing machine differs in scale from any real computing agent.
Question
List three practical consequences arising from unsolvable programs related to the halting problem.
Question
Discuss the ways in which a Turing machine does or does not satisfy the requirement that an algorithm be a well-ordered collection.
Question
Describe in detail what a Turing machine includes.
Question
According to its definition, what must an algorithm be or do?
Question
Discuss at length the assertion that Turing machines define the limits of computability.
Question
What do we require any computing agent to be able to do?
Question
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
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?
Unlock Deck
Sign up to unlock the cards in this deck!
Unlock Deck
Unlock Deck
1/49
auto play flashcards
Play
simple tutorial
Full screen (f)
exit full mode
Deck 12: Models of Computation
1
The model of a phenomenon must capture the full functionality of the real thing.
False
2
Prototypes are an important way of studying many physical and social phenomena._________________________
False
- Models
3
There is no limit to the amount of ____________________ available on a Turing machine.
memory
4
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.
Unlock Deck
Unlock for access to all 49 flashcards in this deck.
Unlock Deck
k this deck
5
Each time a Turing machine operation is done, four actions take place._________________________
Unlock Deck
Unlock for access to all 49 flashcards in this deck.
Unlock Deck
k this deck
6
A formal basis for mathematical proofs guarantees the presence of intuitive statements.
Unlock Deck
Unlock for access to all 49 flashcards in this deck.
Unlock Deck
k this deck
7
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.
Unlock Deck
Unlock for access to all 49 flashcards in this deck.
Unlock Deck
k this deck
8
The Turing machine must execute instructions in the order that the instructions are numbered.
Unlock Deck
Unlock for access to all 49 flashcards in this deck.
Unlock Deck
k this deck
9
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.
Unlock Deck
Unlock for access to all 49 flashcards in this deck.
Unlock Deck
k this deck
10
In binary representation, any unsigned whole number n is encoded by a sequence of n + 1 1s._________________________
Unlock Deck
Unlock for access to all 49 flashcards in this deck.
Unlock Deck
k this deck
11
In any collection of Turing machine instructions, there can be two different instructions that both begin with the same current state and current symbol.
Unlock Deck
Unlock for access to all 49 flashcards in this deck.
Unlock Deck
k this deck
12
A Turing machine cannot produce output.
Unlock Deck
Unlock for access to all 49 flashcards in this deck.
Unlock Deck
k this deck
13
A Turing machine includes a(n) tape that extends infinitely in both directions._________________________
Unlock Deck
Unlock for access to all 49 flashcards in this deck.
Unlock Deck
k this deck
14
Every problem has an algorithmic solution.
Unlock Deck
Unlock for access to all 49 flashcards in this deck.
Unlock Deck
k this deck
15
The Turing machine contains two separate units, one for input and one for output.
Unlock Deck
Unlock for access to all 49 flashcards in this deck.
Unlock Deck
k this deck
16
The bit inverter Turing machine should have two states._________________________
Unlock Deck
Unlock for access to all 49 flashcards in this deck.
Unlock Deck
k this deck
17
The real value of Turing machines as models of computability is in exposing problems that are ____________________.
Unlock Deck
Unlock for access to all 49 flashcards in this deck.
Unlock Deck
k this deck
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.
Unlock Deck
Unlock for access to all 49 flashcards in this deck.
Unlock Deck
k this deck
19
Models can only give us information about existing phenomena.
Unlock Deck
Unlock for access to all 49 flashcards in this deck.
Unlock Deck
k this deck
20
A computing agent must be able to act in accordance with ____________________ instructions.
Unlock Deck
Unlock for access to all 49 flashcards in this deck.
Unlock Deck
k this deck
21
What are four characteristics of the model of a physical or social phenomenon?
Unlock Deck
Unlock for access to all 49 flashcards in this deck.
Unlock Deck
k this deck
22
A tape is used to hold the ____ to the Turing machine.

A) alphabet
B) input
C) output
D) halting state
Unlock Deck
Unlock for access to all 49 flashcards in this deck.
Unlock Deck
k this deck
23
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
Unlock Deck
Unlock for access to all 49 flashcards in this deck.
Unlock Deck
k this deck
24
A(n) ____ is a statement advanced for consideration and maintained by argument.

A) algorithm
B) contradiction
C) thesis
D) 5-tuple
Unlock Deck
Unlock for access to all 49 flashcards in this deck.
Unlock Deck
k this deck
25
Turing machines define the limits of ____, which is what can be done by symbol manipulation algorithms.

A) computability
B) extensibility
C) compatibility
D) correspondence
Unlock Deck
Unlock for access to all 49 flashcards in this deck.
Unlock Deck
k this deck
26
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
Unlock Deck
Unlock for access to all 49 flashcards in this deck.
Unlock Deck
k this deck
27
In a state diagram, ____ are used to represent states.

A) arrows
B) circles
C) rectangles
D) triangles
Unlock Deck
Unlock for access to all 49 flashcards in this deck.
Unlock Deck
k this deck
28
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
Unlock Deck
Unlock for access to all 49 flashcards in this deck.
Unlock Deck
k this deck
29
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
Unlock Deck
Unlock for access to all 49 flashcards in this deck.
Unlock Deck
k this deck
30
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
Unlock Deck
Unlock for access to all 49 flashcards in this deck.
Unlock Deck
k this deck
31
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
Unlock Deck
Unlock for access to all 49 flashcards in this deck.
Unlock Deck
k this deck
32
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
Unlock Deck
Unlock for access to all 49 flashcards in this deck.
Unlock Deck
k this deck
33
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
Unlock Deck
Unlock for access to all 49 flashcards in this deck.
Unlock Deck
k this deck
34
A(n) ____ is a visual representation of a Turing machine algorithm.

A) parity bit
B) model
C) state diagram
D) incrementer
Unlock Deck
Unlock for access to all 49 flashcards in this deck.
Unlock Deck
k this deck
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
Unlock Deck
Unlock for access to all 49 flashcards in this deck.
Unlock Deck
k this deck
36
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
Unlock Deck
Unlock for access to all 49 flashcards in this deck.
Unlock Deck
k this deck
37
State ____ is always the start-up state of the Turing machine.

A) 0
B) 1
C) L
D) R
Unlock Deck
Unlock for access to all 49 flashcards in this deck.
Unlock Deck
k this deck
38
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
Unlock Deck
Unlock for access to all 49 flashcards in this deck.
Unlock Deck
k this deck
39
The term unary means that we will use ____ symbol(s).

A) one
B) two
C) three
D) four
Unlock Deck
Unlock for access to all 49 flashcards in this deck.
Unlock Deck
k this deck
40
A formal basis for proofs might allow for ____ theorem-proving.

A) unsolvable
B) mechanical
C) indisputable
D) observable
Unlock Deck
Unlock for access to all 49 flashcards in this deck.
Unlock Deck
k this deck
41
Explain how a Turing machine differs in scale from any real computing agent.
Unlock Deck
Unlock for access to all 49 flashcards in this deck.
Unlock Deck
k this deck
42
List three practical consequences arising from unsolvable programs related to the halting problem.
Unlock Deck
Unlock for access to all 49 flashcards in this deck.
Unlock Deck
k this deck
43
Discuss the ways in which a Turing machine does or does not satisfy the requirement that an algorithm be a well-ordered collection.
Unlock Deck
Unlock for access to all 49 flashcards in this deck.
Unlock Deck
k this deck
44
Describe in detail what a Turing machine includes.
Unlock Deck
Unlock for access to all 49 flashcards in this deck.
Unlock Deck
k this deck
45
According to its definition, what must an algorithm be or do?
Unlock Deck
Unlock for access to all 49 flashcards in this deck.
Unlock Deck
k this deck
46
Discuss at length the assertion that Turing machines define the limits of computability.
Unlock Deck
Unlock for access to all 49 flashcards in this deck.
Unlock Deck
k this deck
47
What do we require any computing agent to be able to do?
Unlock Deck
Unlock for access to all 49 flashcards in this deck.
Unlock Deck
k this deck
48
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?
Unlock Deck
Unlock for access to all 49 flashcards in this deck.
Unlock Deck
k this deck
49
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?
Unlock Deck
Unlock for access to all 49 flashcards in this deck.
Unlock Deck
k this deck
locked card icon
Unlock Deck
Unlock for access to all 49 flashcards in this deck.