3: Turing machines Flashcards
What is a TM?
A mathematical model of a hypothetical computing machine which manipulates symbols on a tape according to a set of rules defined in states and transitions to find an end result.
How do you define a TM?
As a tuple of 7 items (Q, Σ, Γ, δ, q0, qa, qr)
- Q is a set of states
- Σ is the input alphabet, not containing the blank symbol, ⏘
- Γ is the tape alphabet. Must contain at least Σ and ⏘, and usually contains additional symbols too.
- δ is the transition function, taking the current state and letter in the current cell, and giving the new state, letter to write to the current cell, and movement left or right. δ : (Q \ {qa, qr}) x Γ → Q x Γ x {L, R}
- q0, qa, and qr are the start, accept, and reject states, respectively, where qa ≠ qr
What is a TM capable of?
A hypothetical model of a machine that can recognise languages that are not (only) context-free and can produce output as well as accepting or rejecting inputs/ It is, therefore, more powerful than a PDA and has more sophisticated memory than a simple stack.
How does a TM work?
Given an initial input on a tape, with tape head over first cell in tape and starting at start state. Repeatedly find next state and letter with transition function from current cell and current state to writing a symbol to the current cell, moving tape hear left or right and then moving into a resultant state as part of the transition. The TM can loop infinitely or halt. If it halts in an accepting state, the TM accepts; else, if it halts in a non-accepting state or has no transition mapping for the current state and letter at any point, the TM rejects.
How are TMs similar to and different from DFAs and PDAs?
Similarities with DFAs and PDAs
- The current tape symbol g ∈ Γ is like an input symbol: just like for a DFA, the combination of it and the current state q ∈ Q completely determine what happens next.
- The input word is the initial word on the tape.
- The state set Q is finite and contains a single start state q0.
- The input alphabet Σ is finite.
- The tape alphabet, Γ, is like the stack alphabet of a PDA, except that it must contain both the input alphabet, Σ, and the ‘blank’ symbol, ⏘.
- The TM can’t tell when it is at the leftmost end of the tape, just as a PDA can’t tell when the stack is empty. Similarly to pushing $ onto the stack at the beginning of running a PDA, each Turing machine generally starts by marking the first cell, so that it can be identified later.
Differences with DFAs and PDAs
1. Unlike a DFA, a Turing machine can write on the tape, instead of just reading input.
Unlike a PDA, a Turing machine can write anywhere on its tape, once it has moved the read/write head to the desired cell. At each step, a Turing machine must move one cell left or one cell right, unless the read/write head
is at the left-most end, when a “move left” instruction results in staying put.
2. There is a single accept state, qa, and a single reject state, qr, and TMs stop as soon as one of these is entered.
What is a TM configuration?
The condition of a TM at any 1 particular time. It is constituted of the state of the machine, the contents of the tape of the TM, and the position of the tape head.
How do you define TM configurations?
A word consisting of all the symbols in the tape before the current cell the tape head is pointing to; current state; the tape symbols fro and after the current cell.
When does a TM accept an input word?
A TM accepts an input word if it leads to a series of transitions between configurations such that the TM halts when in a configuration in which the current state is an accepting state.
What does it mean for a language to be recognised by a TM and Turing-recognisable?
If a language is recognised by a TM when it is the set of all the strings the TM accepts. A language is Turing recognisable when there exists a TM that recognises it, so there is a TM with the same language as the language in question.
How can you define a TM with tables?
Construct a table of current states against possible inputs; each cell represents a certain symbol being read in a certain state and will describe what to write to the tape, how to move the tape head, and the new state to transition to.
True/false: Consider 2 finite alphabets, A and B, where A ⊂ B and ⏘ ∈ B \ A : A is a proper subset of B and the blank symbol is in B and not in A.
a) There exists a TM that on input w ∈ A* will halt with ww on the tape.
b) For any word u ∈ B, there exists a TM on input w ∈ A that will halt with uw on the tape.
True
Consider 2 finite alphabets, A and B, where A ⊂ B and ⏘ ∈ B \ A : A is a proper subset of B and the blank symbol is in B and not in A.
Prove that:
a) There exists a TM that on input w ∈ A* will halt with ww on the tape.
b) For any word u ∈ B, there exists a TM on input w ∈ A that will halt with uw on the tape.
??
How do tapes on TMs work?
End at the left side, from which tape is infinite: half-infinite. Consists of symbols or letters in cells. A tape head marks the current symbol. The transition function of the TM describes what to do for each symbol at current cell (cell pointed to by tape head); writes a new letter to the current cell, tape head moves left/right (if at left and end and left move don’t move), and TM goes to a new state.
What does A−B mean (give), given that A and B are sets? How is this sometimes alternatively notated?
The difference between sets A and B: returns items in set A that are not in set B. Sometimes notated as A \ B.
What is a multi-tape TM?
A TM in which there are multiple tapes and the transition function uses the symbol in the current cell of each (or multiple) cells as input as opposed to just from one tape. One immutable tape is sometimes reserved to just hold input. All tapes share the same tape alphabet (apart from when there’s a dedicated input tape which will take the input alphabet).
