Theory of Computation

• Problem solving


  The process of finding a solution to a difficult or complex issue
• Algorithms


  • Sequences of steps that can be followed to complete a task
  • Always terminate rather than going on forever in a loop
  • Can be written in pseudocode; a way of describing instructions that is independent of any particular programming language
  • Pseudocode allows different programmers to communicate algorithms to one another
• Assignment in pseudocode


  Assignment is the process of giving a value to a variable or constant

  • In pseudocode, assignment is represented using an arrow pointing towards the variable or constant that is being given a value
• Sequence in pseudocode


  Sequence is the name given to instructions that follow on from one another

  • Operations will be executed in the order that they appear
• Selection in pseudocode


  Selection is the process of choosing an action to take based on the result of a comparison of values

  • Different actions can be taken depending on the result of a comparison
  • The statements IF, ELSE IF, ELSE and END IF can all be used
• Iteration in pseudocode


  Iteration is the process of repeating an operation

  • Iteration structures include FOR and WHILE loops
  • The code within an iteration structure is indented, allowing for easy identification of different loops
• Abstraction


  The name given to the process of omitting unnecessary details from a problem

  • When solving a problem, abstraction can be used to simplify the problem which can in turn make finding a solution easier
  • There are two distinct forms of abstraction:
  • Representational abstraction
  • Abstraction by generalisation/categorisation
• Representational abstraction 


  A representation of a problem arrived at by removing unnecessary details from the problem.
• Abstraction by generalisation/categorisation


  A grouping by common characteristics to arrive at a hierarchical relationship of the “is a kind of” type.
• Information hiding


  Defined as the process of hiding all details of an object that do not contribute to its essential characteristics

  • Used in problem solving to simplify a problem without changing the essence of the issue
• Procedural abstraction


  Involves breaking down a complex model into a series of reusable procedures

  • The actual values used in a computation are abstracted away and a computational method is achieved
• Functional abstraction


  Procedural abstraction results in a procedure

  • Functional abstraction is the process of abstracting the result of procedural abstraction
  • Abstracting a procedure further disregards the particular method of a procedure and results in just a function
• Data abstraction


  Forms the basis of abstract data types

  • Specific details of how data is actually represented are abstracted away
  • This allows new kinds of data structures to be created from previously defined data structures
• Problem abstraction/reduction


  Details are removed from a problem until it is represented in a way that is solvable

  • A simplified problem is often similar to a problem that has already been solved, meaning that a solution for the problem can be found
• Decomposition


  A problem is divided into a series of smaller sub-problems

  • These smaller problems can be solved individually or further divided until all parts of the original problem have been solved
• Composition


  Can be used to combine procedures to form a larger system

  • Used in abstract data types, where a complex abstract data type is formed for smaller and simpler data types
• Automation


  The process of putting abstractions of real world phenomena into action to solve problems

  • These abstractions are referred to as models
  • Achieved by creating algorithms which are later implemented in code, implementing models in data structures and finally executing the code on the data structures
• Context-free languages


  • Sets of strings and symbols that follow the rules of a context-free grammar
  • Context-free grammars describe which strings are and are not possible in a language by laying out production rules
  • A production rule is as simple as replacing one character for another
  • Examples of production rules include:
  • a -> ab: The a character can be replaced by the two characters ab
  • a -> aa: The a character can be replaced by two a characters
  • b -> a: A b character can be replaced by an a character
• Backus-Naur form


  A way of notating context-free languages

  • Uses statements in which the left-hand side is defined by the right-hand side
• Non-terminals (Backus-Naur form) 


  Text which is placed inside of angle brackets represents a non-terminal

  • Sometimes also called meta-components or syntactic variables
  • Can be broken down further into either more non-terminals, terminals or a combination of the two
• Terminals (Backus-Naur form)


  Text without any brackets represents a terminal

  • Cannot be broken down any further
  • Must be taken to be the written value
  • The pipe symbol (a straight vertical line) represents the OR operator
• Recursion in Backus-Naur form

  Backus-Naur form can make use of recursion

  • A non-terminal can be defined in terms of itself, allowing for recursion to occur
  • Backus-Naur form is capable of representing some strings that cannot be represented by regular expressions as regular expressions cannot support recursion like Backus-Naur form can
• Syntax diagrams


  A visual representation of a regular language

  • Non-terminals are represented by rectangles
  • Terminals are represented by ellipses
  • The shapes are joined by arrows which indicate how strings can be formed from the definitions
  • Each non-terminal is defined by its own syntax diagram

  
• Turing machines


  Formal models of computation
• Turing machines


  • Consist of a finite state machine
  • A read/write head
  • A tape that is infinitely long in one direction and divided into cells
• Tape cell


  Can be left blank or contain a symbol
• Alphabet


  The set of symbols used by a Turing machine
• A Turing machine's alphabet must be finite
• Turing machine


  • Runs a single program, defined by a finite state machine
  • Has a single start state
  • May have a number of halting states
• Halting state


  • Can be entered at any point in the machine's execution
  • Is entered once all of the input data has been processed
• Turing machines


  • More powerful than finite state machines as a model of computation
  • Can utilise a greater range of languages thanks to their infinitely long tape
• Transition functions


  • Can be used to define the rules followed by Turing machines
  • Written in the form delta(current state, read) = (new state, write, move)
  • Have an equivalence with transition rules in a state transition diagram

  
• Universal Turing machines


  Can represent any finite state machine

  • Read a description of a finite state machine from the same tape as the input data
  • Can be said to act as interpreters because they read their instructions in sequence before executing operations
• The importance of Turing machines


  Turing machines provide a definition of what is computable

  • Turing machines can be used to prove that there are problems which cannot be solved by computers