Theory Of Computation Flashcards
Define algorithm
A sequence of steps that can be followed to complete a task and that always terminates
What is representational abstraction?
Representation arrived at by removing unnecessary details
What is abstraction by generalisation/categorisation?
Grouping by common characteristics to arrive at a hierarchical relationship of the ‘is kind of’ type
What does procedural abstraction represent?
A computational method
What is a computational method or pattern?
The result of abstracting away the actual values used in any particular computation is a computational pattern or method (procedure)
What is information hiding
The process of hiding all details of an object that do not contribute to its essential characteristics
What happens to the particular computation method in functional abstraction?
It is hidden
What is the result of procedural abstraction
A procedure, not a function
What abstraction can get you a function
Functional abstraction - disregards the particular computation method
Define data abstraction
A methodology that enables us to isolate how a compound data object is used from the details of how it is constructed ie. Stack implemented as an array and pointer for top of stack
What is problem abstraction?
When details are removed until the problem is represented in a way that it is possible to solve the problem
Define procedural decomposition
Breaking a problem into a number of sub-problems so that each sub-problem accomplishes an identifiable task which might itself be further subdivided
How can you build a compositional abstraction?
By combining procedures to form compound procedures
How can you build data abstraction?
By combining data objects to form compound data for example a tree data structure
What does automation require?
Putting models into action to solve problems
How does automation achieve its requirements
- creating algorithms
- implementing algorithms in program code
- implementing models in data structures
- executing the code
What is a mealy machine used for?
It is used to map an input string to an output string
How is it similar/dissimilar to a Turing machine
Acts as a Turing machine but gives an output as well to create a new string of outputs
How can a Turing machine be viewed as?
A computer with a single fixed program
What are states that have no outgoing states called?
Halting states
What are the 3 main components of a Turing machine?
-read/write head-looks at one square at a time on the tape
- CU - effectively the FSM
- infinite tape - contains a list of acceptable characters for a given Turing machine
What is the difference between a Turing machine and a universal Turing machine?
UTM acts as an interpreter for TM
UTM defines what is actually computable
UTM uses an input string which is a description for the TM
A Turing machine is a desc of a…
Single algorithm
A UTM can…
Tackle any computable problem
