4 - Theory of Computation

Question 1

What does the term algorithm mean?

Answer 1

An algorithm is a sequence of steps that can be followed to complete a task and that can be completed in finite time.

Question 2

What does a double circle indicate in a FSA?

Answer 2

Accepting state.

Question 3

Explain the functionality of the * metacharacter when it is used in a regular expression.

Answer 3

Zero or more of the preceding value.

Question 4

Explain the functionality of the ? metacharacter when it is used in a regular expression.

Answer 4

Zero or one of the preceding value.

Question 5

Describe the significance of the Halting problem for commutation.

Answer 5

The Halting problem demonstrates that there are some problems that cannot be solved by a computer.

Question 6

What is the question posed by the by the Halting problem?

Answer 6

Is it possible in general to write a program that can tell, given any program and its inputs, and without running the program, whether the given program with its given inputs will halt?

Question 7

Why is it not possible to create a Turing machine that solves the Halting problem?

Answer 7

The Halting problem is non-computable