Introduction to Automata Quiz

Any problem can always be reduced to a decision problem.

• True
• False
• Only some problems can be reduced
• Decision problems are unrelated to other problems

A correspondence between a collection of possible input values and a collection of output values such that each possible input is assigned a unique output.

• Mapping
• Relation
• Function
• Association

Functions that are so complex that there is no well-defined step-by-step process for determining their output based on their input values.

• Computable functions

• Deterministic algorithms

• Recursive functions

• Non-computable functions

Which of the following statements IS TRUE?

• Computable functions study the ultimate capabilities of machines.

• Solutions to problems require the evaluation of a computable function.

• Computers can only perform computations described by functions.

• All decision problems are non-computable.

Which of the following statements IS NOT TRUE about a Turing machine?

• A Turing machine can recognize regular languages.

• A Turing machine can be implemented using finite state machines.

• A Turing machine cannot perform basic computations.

• A Turing machine can simulate any algorithm.

A function is computable if it can be computed by a Turing Machine.

• Probably true

• False

• True

• Probably True

Which of the following DOES NOT belong to the group?

• Bin Packing

• Graph Coloring

• Travelling Salesman Algorithm

• Quicksort

If a function cannot be computed by a Turing Machine, then it is said to be:

• computable
• decidable
• recursive
• non-computable