stud
bud
Sign up
Log in
Home
Library
Explore
SAT
More
The Turing Machine, UTMs and the Halting problem Flashcards | StudBud
Explore
/
The Turing Machine, UTMs and the Halting problem
The Turing Machine, UTMs and the Halting problem
20 terms
·
StudBud Administration
·
189 plays
#Alevel #ComputerScience
Flashcards
20 cards
F
Practice quiz
P
Host live
L
Questions
20
Answers
1
Which of the following describes the input to a Universal Turing Machine?
A program written in binary
A finite automaton and its input string
A Turing machine description and its input
A string of random characters
2
How does a Universal Turing Machine differ from a regular Turing machine (TM)?
It has an infinite number of states
It can compute faster than any TM
It uses a different set of symbols than a regular TTM
It can simulate any TM, while a regular TM is specific to a single task
3
What did Alan Turing prove about the Halting Problem in 1936?
That no algorithm can solve the Halting Problem for all Turing machines
That it can be solved only for non-recursive functions
That it is possible to design an algorithm to solve it
That the problem could be solved using a Universal Turing Machine
4
Look at the table. If the current state is S1 and the output is 1, what is the input?
1
blank
0
There isn't one
5
What makes a Universal Turing Machine "universal"?
Its ability to solve problems without a specific algorithm
Its ability to run any algorithmic process
Its ability to solve undecidable problems
Its ability to emulate any finite automaton
6
Look at the diagram. If the next state is SH and the output is 1, what is the current state?
SH
There isn't one
S0
S1
7
What is a Universal Turing Machine (UTM)?
A machine that operates faster than any other machine
A machine that can solve any problem
A machine that has infinite memory
A machine that can simulate the behaviour of any other Turing machine
8
Which of these is
not
a component of a Turing Machine?
A Read-Write Head
Tape
Table of Instructions
Processor
9
What is the Halting Problem?
The problem of determining if a given program will stop with a given input
The problem of determining whether a given input halts
The problem of determining if a finite automaton will halt
The problem of whether a Turing machine has infinite states
10
Why is the Halting Problem significant in computer science?
It proves that some problems are unsolvable by any algorithm
It shows that no problem can be solved by a Turing machine
It proves that every problem can be solved by a universal machine
It demonstrates that Turing machines are unreliable
11
In the Instruction δ(S1, □) = (S2, 1, R) what is in the current cell?
0
δ
Blank
1
12
In the Instruction δ(S1, □) = (S2, 1, R) what is written to the current cell?
Blank
1
0
δ
13
Look at the table. If the current state is S1 and the next state is S1, what is the output?
1
blank
There isn't one
0
14
What the importance of the theory of Turing machines to the subject of computation.
No computing device can be more powerful than a Turing machine
Defines a method for generating artificial intelligence
Turing machines provide a definition of what is computable
Turing machines provide a model of computation
15
Which of the following is true about the Halting Problem?
It can be solved by modern computers with sufficient resources
It is solvable for all Turing machines
It is solvable only for finite input sizes
It is undecidable for a general Turing machine
16
Why can a Universal Turing Machine be considered to be more powerful than any computer that you can purchase?
Because it has an infinite amount of memory
Because it can compute any computable algorithm
Because it can run forever
Because it can simulate behaviour of other Turing machines
17
Which of the following is an implication of the Halting Problem being undecidable?
It is impossible to predict the runtime of any program
A Universal Turing Machine cannot be built
All algorithms must eventually halt
There exist problems that no computer can solve
18
Look at the diagram. If the current state is S0 and the input is 1, what is the next state?
S1
SH
S0
There isn't one
19
The Transition Function is represented by which symbol?
Delta: δ
Gamma: γ
Beta: β
Alpha: α
20
In the Instruction δ(S2, □ ) = (SH, □, R) what is written to the current cell?
1
0
Blank
δ
