Theory of Computation.


In theoretical computer science and mathematics, the theory of computation is the branch that deals with how efficiently problems can be solved on a model of computation, using an algorithm.

i think that Philosophy, Ideas, Innovations & Solutions are also part of Computational Theory - they are part of models or algorithms.

Models of Computation.

In computability theory and computational complexity theory, a model of computation is the definition of the set of allowable operations used in computation and their respective costs.

Models of Computation include:

- Finite State Automatons,
- Stack Machines,
- Turing Machines,
- perhaps more.

Three major branches of Theory of Computation.

- Automata theory.

Automata theory is the study of abstract machines (or more appropriately, abstract 'mathematical' machines or systems) and the computational problems that can be solved using these machines.

These abstract machines are called automata.

Stitie Machine is example of such.

- Computability theory.

Computability theory deals primarily with the question of the extent to which a problem is solvable on a computer.

- Computational complexity theory.

Complexity theory considers not only whether a problem can be solved at all on a computer, but also how efficiently the problem can be solved.

Two major aspects are considered: time complexity and space complexity, which are respectively how many steps does it take to perform a computation, and how much memory is required to perform that computation.

Not all problems can be solved in 'sane' amount of time using 'sane' amount of resources such as memory or printer paper.


i should start at some point measuring costs of operations of a Stitie Machine & Stitie Space models, as well as try to prove their correctness, checking stop conditions in process.

this will happen with time, if i can.

then should consider problems & algorithms compatibility with these models.

See also: [7], [4], [19], Stitie Machine (Maszyna Stanikowa Wysockiego), perhaps more.

No comments:

Post a Comment