1. Finite automata are good models for devices that have a small amount of memory. Pushdown automata are good models for devices that have an unlimited memory that is usable only in the last in, first out manner of a stack.
2. Similar to a finite automaton but with an unlimited and unrestricted memory, a Turing machine is a much more accurate model of a general purpose computer.
3. Note that Z does not contain the blank symbol, so the first blank appearing on the tape marks the end of the input.
4. As a Turing machine computes, changes occur in the current state, the current tape contents, and the current head location. A setting of these three items is called a configuration of the Turing machine.
5. Call a language Turing-decidable or simply decidable if some Turing machine decides it.
6. Every decidable language is Turing-recognizable.
7. A Turing machine is a general example of a CPU that controls all data manipulation done by a computer, with the canonical machine using sequential memory to store data. More specifically, it is a machine (automaton) capable of enumerating some arbitrary subset of valid strings of an alphabet; these strings are part of a recursively enumerable set.
8. In computability theory, the halting problem is the problem of determining, from a description of an arbitrary computer program and an input, whether the program will finish running or continue to run forever.
9. Alan Turing proved in 1936 that a general algorithm to solve the halting problem for all possible program-input pairs cannot exist. A key part of the proof was a mathematical definition of a computer and program, which became known as a Turing machine; the halting problem is undecidable over Turing machines. It is one of the first examples of a decision problem.
10. A Turing machine that is able to simulate any other Turing machine is called a universal Turing machine (UTM, or simply a universal machine).
11. It is often said that Turing machines, unlike simpler automata, are as powerful as real machines, and are able to execute any operation that a real program can.
12. Turing machines are not intended to model computers, but rather they are intended to model computation itself.
14. Anything a real computer can compute, a Turing machine can also compute.
15. In this section we describe some of these variants and the proofs of equivalence in power. We call this invariance to certain changes in the definition robustness. Both finite automata and pushdown automata are somewhat robust models, but Turing machines have an astonishing degree of robustness.
16. we can convert any TM with the "stay put" feature to one that does not have it. We do so by replacing each stay put transition with two transitions, one that moves to the right and the second back to the left.
17. Theorems and proofs are the heart and soul of mathematics and definitions are its spirit.
18. The computation of a nondeterministic Turing machine is a tree whose branches correspond to different possibilities for the machine.
19. The idea behind the simulation is to have D try all possible branches of N's nondeterministic computation. If D ever finds the accept state on one of these branches, D accepts. Otherwise, D's simulation will not terminate
20. All share the essential feature of Turing machines-namely, unrestricted access to unlimited memory distinguishing them from weaker models such as finite automata and pushdown automata.
21. Any two computational models that satisfy certain reasonable requirements can simulate one another and hence are equivalent in power.
22. Informally speaking, an algorithm is a collection of simple instructions for carrying out some task. Commonplace in everyday life, algorithms sometimes are called procedures or recipes.
23. A polynomial is a sum of terms, where each term is a product of certain variables and a constant called a coefficient.
24. He did not use the term algorithm but rather "a process according to which it can be determined by a finite number of operations.
25. The definition came in the 1936 papers of Alonzo Church and Alan Turing. Church used a notational system called the A-calculus to define algorithms. Turing did it with his "machines." These two definitions were shown to be equivalent. This connection between the informal notion of algorithm and the precise definition has come to be called the Church-Turing thesis.
26. Intuitive Notions of Algorithms = Turning Machine Algorithms
27. We have come to a turning point in the study of the theory of computation. We continue to speak of Turing machines, but our real focus from now on is on algorithms. That is, the Turing machine merely serves as a precise model for the definition of algorithm. We skip over the extensive theory of Turing machines themselves and do not spend much time on the low-level programming of Turing machines. We need only to be comfortable enough with Turing machines to believe that they capture all algorithms.
28. The input to a Turing machine is always a string. If we want to provide an object other than a string as input, we must first represent that object as a string. Strings can easily represent polynomials, graphs, grammars, automata, and any combination of those objects. A Turing machine may be programmed to decode the representation so that it can be interpreted in the way we intend. Our notation for the encoding of an object 0 into its representation as a string is (0).
29. In our format, we describe Turing machine algorithms with an indented segment of text within quotes. We break the algorithm into stages, each usually involving many individual steps of the Turing machine's computation. We indicate the block structure of the algorithm with further indentation. The first line of the algorithm describes the input to the machine. If the input description is simply w, the input is taken to be a string. If the input description is the encoding of an object as in (A), the Turing machine first implicitly tests whether the input properly encodes an object of the desired form and rejects it if it doesn't.
30. the Turing machine as a model of a general purpose computer and defined the notion of algorithm in terms of Turing machines by means of the Church-Turing thesis.
31. You are probably familiar with solvability by algorithms because much of computer science is devoted to solving problems. The unsolvability of certain problems may come as a surprise
32. First, knowing when a problem is algorithmically unsolvable is useful because then you realize that the problem must be simplified or altered before you can find an algorithmic solution. Like any tool, computers have capabilities and limitations that must be appreciated if they are to be used well.
33. The second reason is cultural. Even if you deal with problems that clearly are solvable, a glimpse of the unsolvable can stimulate your imagination and help you gain an important perspective on computation.
34. Showing that the language is decidable is the same as showing that the computational problem is decidable.
35. language is decidable is the same as showing that the computational problem is decidable.
36. for decidability purposes, presenting the Turing machine with a DFA, NFA, or regular expression are all equivalent because the machine is able to convert one form of encoding to another.
37. The problem of determining whether a CFG generates a particular string is related to the problem of compiling programming languages.
38. The general problem of software verification is not solvable by computer.
39. The proof of the undecidability of the halting problem uses a technique called diagonalization, discovered by mathematician Georg Cantor in 1873.
40. we can't use the counting method to determine the relative sizes of infinite sets.
41. Cantor proposed a rather nice solution to this problem. He observed that two finite sets have the same size if the elements of one set can be paired with the elements of the other set. This method compares the sizes without resorting to counting. We can extend this idea to infinite sets.
42. A set A is countable if either it is finite or it has the same size as M.
43. The preceding theorem has an important application to the theory of computation. It shows that some languages are not decidable or even Turing recognizable, for the reason that there are uncountably many languages yet only countably many Turing machines. Because each Turing machine can recognize a single language and there are more languages than Turing machines, some languages are not recognized by any Turing machine. Such languages are not Turing-recognizable, as we state in the following corollary.
44. a compiler is a program that translates other programs. A compiler for the language Pascal may itself be written in Pascal, so running that program on itself would make sense.
45. the complement of a language is the language consisting of all strings that are not in the language.
46. Turing machine as our model of a general purpose computer.
47. the primary method for proving that problems are computationally unsolvable. It is called reducibility
48. A reduction is a way of converting one problem to another problem in such a way that a solution to the second problem can be used to solve the first problem.
49. In terms of computability theory, if A is reducible to B and B is decidable, A also is decidable. Equivalently, if A is undecidable and reducible to B, B is undecidable. This last version is key to proving that various problems are undecidable.
50. our method for proving that a problem is undecidable will be to show that some other problem already known to be undecidable reduces to it.
51. But you may not be able to determine whether M is looping, and in that case your simulation will not terminate. That's bad, because you are a decider and thus never permitted to loop.
52. The computation history method is an important technique for proving that ATM is reducible to certain languages.
53. Computation histories are finite sequences. If A doesn't halt on w, no accepting or rejecting computation history exists for M on w.
54. The idea for detecting when M is looping is that, as M computes on w, it goes from configuration to configuration. If M ever repeats a configuration it would go on to repeat this configuration over and over again and thus be in a loop.
55. If M on w has not halted within qngn steps, it must be repeating a configuration according to Lemma 5.8 and therefore looping. That is why our algorithm rejects in this instance.
56. Roughly speaking, being able to reduce problem A to problem B by using a mapping reducibility means that a computable function exists that converts instances of problem A to instances of problem B. If we have such a conversion function, called a reduction, we can solve A with a solver for B. The reason is that any instance of A can be solved by first using the reduction to convert it to an instance of B and then applying the solver for B. A precise definition of mapping reducibility follows shortly.
57. A Turing machine computes a function by starting with the input to the function on the tape and halting with the output of the function on the tape.
58. All usual arithmetic operations on integers are computable functions
59. represent computational problems by languages.
60. A mapping reduction of A to B provides a way to convert questions about membership testing in A to membership testing in B.
61. If one problem is mapping reducible to a second, previously solved problem, we can thereby obtain a solution to the original problem.
62. The recursion theorem is a mathematical result that plays an important role in advanced work in the theory of computability. It has connections to mathematical logic, the theory of self-reproducing systems, and even computer viruses.
63. The same reasoning applies to any machine A that constructs a machine B: A must be more complex than B. But a machine cannot be more complex than itself. Consequently, no machine can construct itself, and thus self-reproduction is impossible.
64. Making machines that reproduce themselves is possible. The recursion theorem demonstrates how
65. The recursion theorem provides the ability to implement the self-referential this into any programming language
66. Mathematical logic is the branch of mathematics that investigates mathematics itself.
67. we sketch the proof of Kurt Godel's celebrated incompleteness theorem. Informally, this theorem says that, in any reasonable system of formalizing the notion of provability in number theory, some true statements are unprovable.
68. The concepts algorithm and information are fundamental in computer science.
69. We define the quantity of information contained in an object to be the size of that object's smallest representation or description. By a description of an object we mean a precise and unambiguous characterization of the object so that we may recreate it from the description alone.
70. we restrict our attention to objects that are binary strings. Other objects can be represented as binary strings, so this restriction doesn't limit the scope of the theory.
71. A finite state machine is a mathematical abstraction used to design algorithms.
72.
Reducibility:
1. For example, suppose that you want to find your way around a new city. You know that doing so would be easy if you had a map. Thus you can reduce the problem of finding your way around the city to the problem of obtaining a map of the city.
2. reducibility says nothing about solving A or B alone, but only about the solvability of A in the presence of a solution to B
3. The problem of traveling from Boston to Paris reduces to the problem of buying a plane ticket between the two cities. That problem in turn reduces to the problem of earning the money for the ticket. And that problem reduces to the problem of finding a job.
Undecidability:
the undecidability of ATM, the problem of determining whether a Turing machine accepts a given input.
ETM is undecidable
RegularTM is undecidable
HALTTM is undecidable
Turing Machine:
1. The Turing machine model uses an infinite tape as its unlimited memory. It has a tape head that can read and write symbols and move around on the tape.
Computing Models:
Finite Automata
Pushdown Automata
Turing Machine
Universal Turing Machine
Theory:
Lambda Calculus
Types of Turing Machines:
Turing Machine
Multitape Turing Machine
Nondeterministic Turing Machine [Use Breadth First Search, not Depth First Search]
Enumerator
Terms:
Definitions
Mathematical Statements
Proofs
Theorems
Lemmas
Corollary
Example
Polynomial:
Term
Coefficient
Root
integral root
Turing Recognizable Language
Recursively Enumerable Language
Turing Machine:
Recognizer
Decider
Turing Machine Algorithms
Algorithmic Solvability
Unsolvability
Terms:
Halting Problem
Correspondance
Uncountable
diagonalization
Co-Turing recognizable
Decidability
Reducibility
Linear bounded Automata/LBA
Undecidability
Post Correspondence Problem /PCP
Modified Post Correspondence Problem/MPCP
Mapping Reducibility
Computable Functions
halt
many-one reducibility
paradox
tenet
fixed point
Precise Language
formula
well-known formula
atomic formula
arity
scope
prenex normal form
free variable
sentence/statement
Univers
model
language of model
oracle turing machine
description language
Theorems:
1. The halting problem is undecidable.
2. a language is decidable exactly when both it and its complement are Turing-recognizable.
3. Rice's theorem, states that testing any property of the languages recognized by Turing machines is undecidable.
4. EQTM is undecidable.
5. Elba is undecidable.
6. ALLcfg is undecidable.
7. PCP is undecidable.
8. Afixed point of a function is a value that isn't changed by application of the function. In this case we consider functions that are computable transformations of Turing machine descriptions. We show that for any such transformation some Turing machine exists whose behavior is unchanged by the transformation. This theorem is sometimes called the fixed-point version of the recursion theorem.
8. Th(N,+) is decidable.
9. Th(N,+,*) is undecidable.
10. Theorem 6.24 shows that a string's minimal description is never much longer than the string itself.
Levels:
1. [Formal Description]The first is the formal description that spells out in full the Turing machine's states, transition function, and so on. It is the lowest, most detailed, level of description.
2. [Implementation Description] The second is a higher level of description, called the implementation description, in which we use English prose to describe the way that the Turing machine moves its head and the way that it stores data on its tape. At this level we do not give details of states or transition function.
3. [High Level Description] Third is the high-level description, wherein we use English prose to describe an algorithm, ignoring the implementation details. At this level we do not need to mention how the machine manages its tape or head.
References:
https://en.wikipedia.org/wiki/Halting_problem
https://en.wikipedia.org/wiki/Partial_function
This comment has been removed by the author.
ReplyDelete