805576
Description
Flashcards by Zacchaeus Snape, updated more than 1 year ago
|
Created by Zacchaeus Snape
over 10 years ago
|
|
| Question | Answer |
| Abstraction | representation that is arrived at by removing unnecessary details |
| Principle of universality | A universal machine is a machine capable of simulating any other machine |
| Interpreter | a program that works its way through a set of instructions, identifying the next instruction then executing it |
| Universal Turing machine | A Turing machine that can execute other Turing machines by simulating the behaviour of any Turing machine |
| Power of a Turing machine | No physical computing device can be more powerful than a Turing machine. If a turing machine cannot solve a yes/no problem, then the problem is not solvable. |
| Equivalent Turing machine | All other types of computing machine are reducible to an equivalent Turing machine |
| Turing machine | An FSM that controls one or more tapes where at least one tape is infinitely long |
| Finite state automation | An FSM that produces no output while processing the input, but responds yes or no when it has finished processing the input |
| Moore machine | An FSM that determines its outputs from the present state only |
| Mealy machine | An FSM that determines its outputs from the present state and from the inputs |
| Halting state | a state that has no outgoing transition |
| Non-deterministic finite state machine | an FSM that may have several possible next states for each pair of state and input symbol |
| Deterministic finite state machine | an FSM that has only one next state for each pair of state and input symbols |
| Transition table | tabulates the transition mappings |
| transition function | maps input symbol and state to the output symbol and state |
| Finite state machine | consists of a set or input symbol, and if it produces and output, a set of output symbols, a finite set of states and a transition function that maps a state-symbol pair to a state and possibly generates an output |
Want to create your own Flashcards for free with GoConqr? Learn more.