Theory of Computation

• Logical Reasoning: The use of a set of facts (axioms) to draw conclusions and determine whether new information is true or false.
• Algorithms: A sequence of steps that can be followed to complete a task and that always terminates.
• Correctness: An algorithm is said to be correct when it is consistent with the specification and produces the expected output for any given input.
• Efficiency: A property of an algorithm that is related to the amount of resources (memory space and time in particular) that an algorithm uses in its execution.
• Hand-tracing: The process of looking at a program’s entire code or code extract and running through the instructions as though you are the computer.
• Pseudo-code: A human-readable method of writing the steps of an algorithm without any particular programming language.
• Abstraction by Generalisation or Categorisation: Simplifying a problem by grouping together common characteristics of a problem to arrive at a hierarchical relationship.
• Representational Abstraction: Simplifying a problem by only taking into consideration the necessary details required to obtain a solution, leaving a representation without any unnecessary details.
• Information Hiding: The process of hiding all details of an object that do not contribute to its essential characteristics.
• Procedural Abstraction: Simplifying a problem by breaking it down into a series of procedures or subroutines that are generalised with variable parameters. Knowledge of the implementation of each procedure is irrelevant.
• Procedure: The result of abstracting away the actual values used in any particular computation is a computational pattern or computational method.
• Functional Abstraction: Simplifying a problem by breaking it down into a series of reusable functions which disregard the particular computational method.
• Data Objects: Data abstractions that hide details of how data are actually represented from the user.
• Problem Abstraction/Reduction: The repeated removal of unnecessary details from a problem until an underlying problem representation is reached which is identical to a previously solved problem.
• Procedural Decomposition: The process of breaking down a problem into a number of sub-problems, so that each sub-problem accomplishes an identifiable task, which might itself be further subdivided.
• Composition Abstraction: The reverse process of decomposition where a complex system of compound procedures is built from its smaller, simpler procedures.
• Data Abstraction Composition: The process of combining data objects to form compound data
• Automation: The process of creating algorithms and implementing them as data structures and models of real-life situations that run without a significant need for human intervention.
• Accepting States: An optional state of a FSM that indicates whether or not an input has been accepted by the FSM
• State Transition Tables: A tabular representation of a FSM that contains the current state, inputs and their consequent successor state.