Theory of Computation
Theory of Computation

- Theory of computation is the study and making of computational models and how they solve problems. Many believe it answers the question of What are the fundamental capabilities and limitations of computers?

- Theory of computation goes back as far as the 1930s. Technology and computers have developed so much since then. The field started off as a section of mathematics, but with time and research it became more complex, branched out, and turned into a field of its own.

- Theory of Computation breaks down into three main sub-sections: Automata theory, computability theory, and complexity theory.

- Automata theory is where scientists study machines and their problem solving abilities. It aids in making computational problem solving more efficient. Both computability and complexity rely on automata.

- The most used computational model is the Turing machine. A Turing machine is a machine that helps solve problems, using a tape that has no more than repeated units of (1), (0), and (). It is believed a turing machine can do more than an actual computer. Recently a challenger has surfaced to challenge the Alan Turing's Turing machine, quantum computers.

- The computability theory answers the question of whether a problem is solvable or not. In the early 1930s experts have realized that computers cannot figure out if a mathematical statement is true or not, oddly computers were not created until the 1940s.

-The complexity theory tries to determine if something is hard or easy to solve using computers, which cannot be determined easily Hard to determine what is easy and what is hard to resolve using computer. Problems are easy to solve when the quantities are small, but real world problems tend to be huge, so they will be harder to solve, which we benefit from.

- The complexity theory is applied in our lives in cryptography, where a more difficult problem is needed to avoid access to those who are unwanted.



Links:

Automata theory

Computability and complexity

Turing machines explained (video)

Introduction to the theory of computation (book)

Theory of computation, wikipedia

complexity and cryptography (video)



Questions:

1) Are computers still unable to figure out if mathematical statements are true or false?
2) Regarding complexity, is a more difficult solution always favorable rather than an easy one?
3) Do quantum computers really challenge Turing machines?



Updated version (with the help of the ARC)


The theory of computation is the study and making of computational models and how machines solve problems. Many believe it answers the question of "What are the fundamental capabilities and limitations of computers?" The theory of computation goes back as far as the 1930s. Technology and computers have developed so much since then. The field started off as a section of mathematics, but with time and research it became more complex, branched out, and turned into a field of its own.

The theory of Computation breaks down into three main sub-sections: automata theory, computability theory, and complexity theory. Automata theory is where scientists study machines and their problem solving abilities. It aids in making computational problem solving more efficient. Both computability and complexity rely on automata. The most used computational model is the Turing machine and it's an example of the theory of automata. A Turing machine is a machine that helps solve problems, using a tape that has no more than repeated units of (1), (0), and (). It is believed a Turing machine can do more than an actual computer. Recently a challenger has surfaced to challenge the Alan Turing's Turing machine, quantum computers.

The computability theory answers the question of whether a problem is solvable or not. In the early 1930s, experts realized that theoretically, computers could not figure out if a mathematical statement is true or not. Oddly, computers were not created until the 1940s.

The complexity theory tries to determine if something is hard or easy to solve using computers, which cannot be determined easily. It is hard to determine what is easy and what is hard to resolve using computer. Problems are easy to solve when the quantities are small, but real world problems tend to be huge, so they will be harder to solve, which we benefit from in computer security. The complexity theory is applied in our lives in cryptography, where a more difficult problem is needed to avoid access to those who are unwanted.