4 - Theory of Computation
No description yet. This curated deck is ready for daily study.
Card preview (7)
What does the term algorithm mean?
An algorithm is a sequence of steps that can be followed to complete a task and that can be completed in finite time.
What does a double circle indicate in a FSA?
Accepting state.
Explain the functionality of the * metacharacter when it is used in a regular expression.
Zero or more of the preceding value.
Explain the functionality of the ? metacharacter when it is used in a regular expression.
Zero or one of the preceding value.
Describe the significance of the Halting problem for commutation.
The Halting problem demonstrates that there are some problems that cannot be solved by a computer.
What is the question posed by the by the Halting problem?
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?
Why is it not possible to create a Turing machine that solves the Halting problem?
The Halting problem is non-computable