Week 5, 6 and 7 - Turing Machines Flashcards
What is a Turing machine made up of?
An infinite tape split into cells. A head positioned above a single cell, that can read and write symbols on the tape and can move along the tape in either direction. The head contains a finite number of states.
What 2 finite sets must a Turing machine have?
The tape alphabet including a blank character.
The set of possible return values
What is a macro?
A single instruction that abbreviates a whole program.
How do you replace a macro with the full program?
Anything that points to the macro, will now point to the initial state of the expanded program. Each return instruction is replaced by a no-op that leads to appropriate state the abbreviated state pointed to.
What are auxiliary characters?
Characters not in the input alphabet and the program must guarantee none will appear in the tape after the execution finishes.
For a multitape Turing machine what must be true about the auxiliary tape?
It must start and finish blank.
What is the complexity class P?
The set of all languages where there is a Turing machine that can decide if a given word is in the language or not in polynomial time.
What is the complexity class NP?
The set of all languages where there is a non-deterministic Turing machine that can decide if a given word is in the language or not in polynomial time.
Why is complexity class P a subset of complexity NP?
Since all Turing machines are also non-deterministic Turing machines, it means all Turing machines are NDTM that run in polynomial time, therefore are an element in both P and NP.
