FoC Final
Terms
undefined, object
copy deck
- define LOOP
- loop is the set of all other strings which loop forever
- Are turing machines deterministic?
- yes
- define utm
- a utm is a tm that accepts a string composed of two parts, an encoded tm and data. no matter the input, the utm will operate on the data as if it were T
- define post machine
- a post machine consists of: an alphabet sigma of input letters plus #; a linear storage location called STORE or QUEUE; read states which remove the leftmost character; add states which concatenate a character to the right end of STORE; a start state and some accept and reject states
- theorem 60
- if L is recursive, then L1 is also recursive
- define recursively enumerable
- a language L over the alphabet sigma is recursively enumerable if there is a TM T that accepts every word in L and either rejects or loops forever for every word in the language L1
- define turing machine
- a turing machine consists of: an alphabet sigma of input letters; a tape divided into a sequence of numbered cells, each containing one character or a blank; a tape head which can read a cell, write a cell, and move to the left or right during each step; an alphabet of characters that can be written to the tape; a finite set of states with exactly one start state and zero or more halt states; a program which is a set of rules which determine what to write and where to move, depending on the current state and input
- theorem 63
- the intersection of two recursively enumerable languages is also recursively enumerable
- theorem 65
- utm's exist
- define recursive
- a language L over the alphabet sigma is called recursive if there is a TM T that accepts every word in L and rejects every word in L1
- theorem 61
- if L and L1 are both re, then L is recursive
- theorem 62
- if T1 and T2 are TMs, then there exists a TM T3 such that accept(T3)=accept(T1)+accept(T2)
- define ACCEPT
- accept is the set of all strings leading to a halt state
- define alan
- alan is all the words in CWL that are not accepted by the TMs they represent or that do not represent any TM
- define REJECT
- reject is the set of all strings which crash during execution