CSE355 Final MC questions & answers
The halting problem is undecidable, this implies that there is no
algorithm to decide whether a given program P terminates on input w
when P and w are both provided as input <P,w>.True or False? - answer
True
The halting problem is undecidable, this implies that for every program
P and every input w, there is no algorithm to decide whether P
terminates on input w. True or False? - answer False, there exists a P for
which an algorithm could decide whether P terminates on w, e.g. if P
were a DFA
The halting problem is undecidable, this implies that Turing machines
are not as powerful as programs in Java. True or False? - answer False,
the Church-Turing thesis says that they are equivalent
The halting problem is undecidable, this implies that there is NO
algorithm to decide whether a given program P that implements a finite
automaton terminates on input w when P and w are both provided as
input <P,w>. True or False? - answer False, the halting problem does not
apply to finite automata, and even if it did, the statement that there is
NO algorithm to decide on P and w is false for finite automata (note
that decidability for finite automata is actually called acceptance)
,The halting problem is undecidable, this implies that there is AN
algorithm to decide whether a given program P that implements a finite
automaton terminates on input w when P and w are both provided as
input <P,w>. True or False? - answer False, being undecidable means
there is NOT an algorithm to decide
To show that a language is NOT decidable, one could reduce an
undecidable language to it. True or False? - answer True
To show that a language is NOT decidable, one could show that it is not
recognizable. True or False? - answer True
To show that a language is NOT decidable, one could use the Church-
Turing thesis. True or False? - answer False, the Church-Turing thesis can
be used to show that a language is decidable or undecidable, but you
may not always be able to apply it
To show that a language is NOT decidable, one could ask 1000 people to
write a program for it and find out that none of them can. True or False?
- answer False, please review the notes and lectures on 1000 people
writing a program, I will not repeat myself here
To show that a language is NOT decidable, one could reduce it to an
undecidable language. True or False? - answer False, it's the other way
, around; you reduce the undecidable language to the one you are trying
to check
To show that a language is decidable, one could write a program in C++
for it, show that the program always halts, and use the Church-Turing
thesis. True or False? - answer True
To show that a language is decidable, one could show the language can
be enumerated by a Turing machine. True or False? - answer False,
enumerable implies recognizable, but recognizable does not imply
decidable
To show that a language is decidable, one could show the language is
well defined. True or False? - answer False, "we didn't talk about well-
defined" (apparently the TAs said this)
To show that a language is decidable, one could use closure properties.
True or False? - answer True
To show that a language is decidable, one could describe a Turing
machine for it and show it always halts. True or False? - answer True
To show that a language is NOT recognizable, one could show that its
complement is recognizable but not decidable. True or False? - answer
The halting problem is undecidable, this implies that there is no
algorithm to decide whether a given program P terminates on input w
when P and w are both provided as input <P,w>.True or False? - answer
True
The halting problem is undecidable, this implies that for every program
P and every input w, there is no algorithm to decide whether P
terminates on input w. True or False? - answer False, there exists a P for
which an algorithm could decide whether P terminates on w, e.g. if P
were a DFA
The halting problem is undecidable, this implies that Turing machines
are not as powerful as programs in Java. True or False? - answer False,
the Church-Turing thesis says that they are equivalent
The halting problem is undecidable, this implies that there is NO
algorithm to decide whether a given program P that implements a finite
automaton terminates on input w when P and w are both provided as
input <P,w>. True or False? - answer False, the halting problem does not
apply to finite automata, and even if it did, the statement that there is
NO algorithm to decide on P and w is false for finite automata (note
that decidability for finite automata is actually called acceptance)
,The halting problem is undecidable, this implies that there is AN
algorithm to decide whether a given program P that implements a finite
automaton terminates on input w when P and w are both provided as
input <P,w>. True or False? - answer False, being undecidable means
there is NOT an algorithm to decide
To show that a language is NOT decidable, one could reduce an
undecidable language to it. True or False? - answer True
To show that a language is NOT decidable, one could show that it is not
recognizable. True or False? - answer True
To show that a language is NOT decidable, one could use the Church-
Turing thesis. True or False? - answer False, the Church-Turing thesis can
be used to show that a language is decidable or undecidable, but you
may not always be able to apply it
To show that a language is NOT decidable, one could ask 1000 people to
write a program for it and find out that none of them can. True or False?
- answer False, please review the notes and lectures on 1000 people
writing a program, I will not repeat myself here
To show that a language is NOT decidable, one could reduce it to an
undecidable language. True or False? - answer False, it's the other way
, around; you reduce the undecidable language to the one you are trying
to check
To show that a language is decidable, one could write a program in C++
for it, show that the program always halts, and use the Church-Turing
thesis. True or False? - answer True
To show that a language is decidable, one could show the language can
be enumerated by a Turing machine. True or False? - answer False,
enumerable implies recognizable, but recognizable does not imply
decidable
To show that a language is decidable, one could show the language is
well defined. True or False? - answer False, "we didn't talk about well-
defined" (apparently the TAs said this)
To show that a language is decidable, one could use closure properties.
True or False? - answer True
To show that a language is decidable, one could describe a Turing
machine for it and show it always halts. True or False? - answer True
To show that a language is NOT recognizable, one could show that its
complement is recognizable but not decidable. True or False? - answer
