12 + 13 Flashcards
What is a multi-track machine? Why is it identical to a standard one track machine
Instead of one tape there are several, this is identical to a one tape machine with an expanded alphabet
What is a two way tape machine? How is it identical to a one tape machine?
The tape is infinite in both directions. This is identical to a two way tape machine but with the 0 cell duplicated. The extra copy of the 0 cell(upper tape) has a # written on it. We then duplicate every state into an upper and lower version, if we would have gone left but are on the section with a # we instead go right and now only focus on the top tape. With each left movement now moving us right and vice versa. This two tape machine is then identical to a one tape machine.
What is a multi tape machine? How is it identical to a one tape machine
Seperate tapes, each with their own read and write head. To represent this as a multi track machine we use 2k + 1 tracks, where k is the number of tapes. 1 is for decoration(# in leftmost square to allow reliable wind back to leftmost cell).
Each tape is dedicated two tracks, one contains the actual contents. The other a single symbol M which marks where the read-write head should be.
A single transition requires us to check the symbol on each virtual tape and storing it via the state the machine is in. We then rewind to the left. Now we determine what to write on each tape and which way to move the head. We then advance to each mark, change the symbol on the virual copy and move the mark as needed. When done go back to the left.
What are the non determinism types in Turing machines
Non determinism by transition: more than one possibility for the read write action, movement direction, or resulting state. If any choice combination leads to success then the word is accepted.
Genie:Ask the Genie to write something on oracle tape, use oracle tape to work out whether the word is accepted by the machine or not. Make sure the question and machine are designed so they can’t be tricked
What is a recursive and recursively enumerable language
A recursively enumerable language is one which is accepted by some turing machine. A recursive language is one which is accepted by a turing machine which will halt on all inputs. The difference is that a recursively enumerable language could cycle forever, a recursive cannot.
What is a language enumerator?
A language enumerator lists the elements of a language in some order, possibly with repetitions but with every element being listed separately, each word will be separated by a symbol not from the alphabet.
prove that if there is a TM that enumerates a language, then there is a TM that enumerates L without repetitions
Augment TM that enumerates L with another output tape, each time a word is added to the output tape check whether it already exists in the tape, if not add to the real output tape, and restart. Else just restart.
Prove that a language L is enumerated by a TM if and only if it is recursively enumerable.
Suppose L is enumerated by M. Build a machine that accepts M by adding an extra input tape on which a word w is written. Each time M produces a new word check if it is equal to w, if so halt and accept. This way is the word is in the language we halt and accept.
To build an enumerator from a recursively enumerable language accepted by some machine T we just build a machine that successively runs T for k steps for all input sequence of length 1-k. Thus eventually we add all accepted words to output tape.
Prove that a language can be enumerated by length if and only if it is recursive.
If L is recursive take machine M that accepts it and halts on all inputs. Run it on each string of length 0, then each of length 1 etc. Each time is accepted add to output tape. Resulting machine enumerates by length. Conversely suppose L is enumeratedby length. If L is finite then it is regular and recursive, so nothing to prove. Otherwise take enumerator by length and desired input word w. Wait until w or some longer word appears, accepting or rejecting accordingly.
If we were to use a set alphabet of {0,1} to encode a turing machine how could we do this?
encode alphabet as 1^1 -1^i where i is the number of elements in alphabet.
A set of states, encoded at 1^1-1^j where j is the number of states.
Direction, let L be 1 and R 11.
Transitions: this is 5 tupples(start,read,write,move,finish) encode these as individual parts seperated by a single 0.
The complete set of transitions, encode each transition and seperate from next using 00.
Use 000 to represent start and end of encoding.
How can we have a universal turing machine?
Use a multi tape machine, input is R(M) w where M is a TM and w an input word. First w is copied to working tape, a third tape registers state and is initialised to 1. The machine can then follow the instructions in the state.
