Unit 4 - Chapter 12 Flashcards
Any computing agent must be able to do the following
1) Accept Input
2) Store Information in and retrieve it from memory
3) Tale actions according to algorithm instructions; the choice of what action to take depend on the present state of the computing agent, as well as on the input item presently being processed.
4) Produce output.
Turing machine
includes a ( conceptual) tape that extends infinitely in both directions. The tape is divides into cells, each of which contains one symbol. The symbols must come from a finite set of symbols called the tape alphabet. The alphabet for a given Turing machine always contain a special symbol b ( for “blank”), usually both of the symbols 0 and 1 ( zero and one), and sometimes a limited number of other symbols, let’s say X and Y, used a placeholders of markers of some kind. At any point in time, only a finite number of the cells contain nonblank symbols.
The details of the actions ( what to write, what the new state is, and which direction to move ) depend on the current state of the machine and on the contents of the tape cell currently being read ( the input).
Turing machine instructions describe these details. Each instructions tells what to do for a specific current state and current input symbol.
Writing a set of Turing machine instructions to allow a Turing machine to carry out a certain task is similar to writing a computer program to
allow a computer to carry out a certain task. We can call such a collection of instructions a Turing machine program.
An algorithm must:
1) Be a well-ordered collection
2) Consist of unambiguous and effectively computable operations
3) Halt in a finite amount of time
4) Produce a result
State diagram
is a visual representation of a Turing machine algorithm, where circles represent states, and arrows represent transitions from one state to another.
Bit inversion
An electronic device called a NOT gate is essentially a bit inverter and is one of the components of a real computer.
Church-Turing Thesis
If these exists an algorithm to do a symbol manipulation task, then there exists a Turing machine to do that task.
Intractable problems
Intractable problems are solvable, but the solution algorithms all require so much work as to be virtually useless. They are not time efficient. But you can’t say they are not doable.
The Hamiltonian circuit problem is suspected to be such a problem, but we don’t really know for sure!
No one has yet found a solution algorithm that works in polynomial time, but neither has anyone proved that such an algorithm does not exist.
Halting problem
Turing machine exists to solve this problem: Given any collection of Turing machine instructions together with any initial tape contents, decide, whether that Turing machine will ever halt if started on that tape.
No Turing machine exist that will give us the answer “Yes, halts” or “No, never halts”.
Theorems
are ideas that can be proved in a formal, mathematical way, such as “ the sum of the interior angles of a triangle equals 180”. The definition of an algorithm is still descriptive, not mathematical.
Turing machines
define the limits of computability, that which can be done by symbol manipulation algorithms.
