Mathesis and Logic
Logic's Mathematization
- First, the idea of logic’s mathematization appeared in the XVII century. The French philosopher and mathematician Rene Descartes considered that the human mind could reach the truth if to reduce the complex ideas to simple ones without avoiding omissions in the logical conclusions. Thus, he recommended using in logic the conventional mathematic methods.
- The German philosopher and mathematician Wilhelm Leibniz proposed to use in logic the mathematic symbolics and pronounced the thought about the binary system of numeration in it. So, mathematic or symbolic logic was born. He formulated the notion "the mathematic logic" and its tasks which were clear for the narrow circle of specialists. Till the middle of the XIX century, it was little known.
- This table reflects partly the way of mathematic logic, its great influence on computer science.
Development of Logic
1. | Aristotle The founder of science about thinking. | The logical doctrine |
2. | Democritus | The term Logic. |
3 | August de Morgan British mathematician and logician. The laws of August de Morgan | . The laws of August de Morgan |
4 | Wilhelm Leibniz | The mathematic logic |
5 | George Boule | Algebra of logic or Boule's Algebra |
6 | William Stanley Jevons | British economist and logician. The logic piano and its using |
7 | Charles Sandy Pierce | The arrow of Pierce |
8 | Maurice Carnot | The tables of Carnot and their practical using |
9 | Pavlo Khruschov | The logic machine |
10 | Olexander Shukarev | The mind's machine |
11 | Platon Poretskiy | Ukrainian and Russian mathematician, logician. intuitive logic |
12 | Lewis Carrol | trhe British mathematician writer. Intuitive logic |
13 | Henry Sheffer | The American logician.The stroke of Sheffer |
14 | Claude Shannon | The theory of links in secret systems |
15 | Gotlib Frege | The founder of the modern mathematical logic. The theory of the content |
16 | John von Neumann | Inventions and theories |
17 | Andrew Dzurak | Quantum cubis and computers |
18 | Edward Forest Moore | The figure automate |
19 | George Mini | The abstract figure automate |
20 | Leonard Aldeman | Biocomputer |
21 | Ehud Shapiro | DNA computer |
22 | SMOS | Complementary-symmetry/metal-oxide semi conductor |
23 | Nano conductors | nano conductors electronic devices |
When It Began
It began in 1994 when Leonard Adleman, professor of computational science at the University of Southern California, proposed an algorithm for using DNA to solve a version of the “traveling salesman problem”. This problem is one of the expressions of the so-called Hamiltonian Path Problem in hard mathematical problems (Hamiltonian Path Problem or HPP), and it involves enumerating a huge number of possible solutions to obtain the optimal one. Adleman with the help of "DNA computing" solved the problem for 7 cities and 13 roads between them, when it is necessary to plot the shortest route of a single visit to each of these cities.
The Most Fruitful Combination
One of the most meaningful and fruitful combination of the biology, logic, and computational science is in the theory of L. Adleman. Aldeman's biocomputer is an extremely interesting application of mathematical logic based on the phenomenon of human nature - DNA - in solving pragmatic problems of the urban environment. At the same time, mathematical logic opens up new possibilities for itself using the architectonics of natural processes. Scientists often call this merger biology, sometimes with critical intonation.
Adleman's Method
- To understand why we and Gifford are right, let's take a quick look at Adleman's method. He labeled each city as a 20-base chunk of single-stranded DNA with random sequences. The roads between every two cities were represented as stretches of complementary single-stranded DNA of 20 bases that span half of the paths between the cities. At the same time, the canonical rule of base pairing in double-stranded DNA is observed: Adenine-Thymine, Guanine-Cytosine. The path between 7 cities begins with a piece of double-stranded DNA that connects any two cities. It is important that there may be more than one DNA fragment denoting one city. Then more than 100 billion radioactively labeled "DNA cities" and "DNA paths" were mixed in a test tube and multiplied by enzymatic DNA amplification. On this, according to Adleman, "DNA computing" ends. Further, to obtain the answer - the optimal path (certain DNA fractions), the reaction mixture with the "response" was electrophoretically separated to obtain all the paths going from the "start" to the "end". Then they singled out those paths that only once passed through 7 cities; identified paths between 7 different cities.
- Moreover, if fractions of "DNA pathways" were found after this stage, then they were considered the most optimal ("winners"). This was the "solution" to the traveling salesman problem. In the process of finding such a "solution", billions of parallel rapidly occurring complementary spontaneous (not human-programmed) acts of "recognition" of single-stranded DNA and billions of spontaneous enzymatic replications of these molecules were involved. At the same time, with a small investment of time and energy, something like a "genetic soup" is formed. Such speed and precision of molecular processes are inconceivable for equivalent operations in digital electronic computers using deterministic information processing vectors. In the case of "DNA computing", it is believed that non-deterministic acts of processing large parallel arrays of numbers and letters (4 nucleotides of DNA) are used.
DNA Molecules
It took only a week to get a response, while traditional computers would take several years. At the same time, a fundamental phenomenon inherent in DNA molecules was used - the ability of its single chains to complementary mutual recognition. This phenomenon consists in the fact that any fragments of each of the two DNA strands are found in solution (or in the chromosomes of a living cell) only their own, in a sense mirror-like, halves and form a normal double helix. This phenomenon is one of the manifestations of the general property of highly organized biostructures and polymeric molecular-supramolecular formations to self-assembly. So in vitro - in vivo ribosomes, membranes, chromosomes, viruses, and phages self-assemble. Including single-stranded DNA. The success and speed of spontaneous searches by halves of DNA for each other, as an act of self-organization (self-assembly), provided a high speed of enumerating options within the "traveling salesman problem".Until recently, the reasons for the rapid and accurate inner recognition of DNA halves were unknown. Moreover, this is extremely important for the real creation of a DNA computer, and this will be discussed below.
Solving the Problem
So, the Algorithm for solving the Hamiltonian path according to Adleman is as follows:
Random paths are represented by a graph,
Only those paths are saved that start (in the case of cities A, B, C, D, E, F, G) from the start in city A and end in city G,
If a city has n cities, only paths in n cities are saved (n = 7),
Only paths that pass all cities once are saved,
Any remaining paths are solutions.
Molecular biological stages of obtaining a solution are reduced to the following operations:
a) synthesis single-stranded DNA,
b) dividing them by length with isolation of 20-base DNA,
c) mixing them in test tubes,
{{ 1}} d) isolation of DNA strands with known sequences,
e) isolation of complementary double-stranded DNA by reassociation,
f) PCR amplification (reproduction) of DNA,
g) cleavage of DNA with restriction enzymes,
h) ligation of DNA complementary at the “sticky” ends,
and) determination of the presence or absence of labeled DNA in test tubes.
Efficiency Will Be...
What is the efficiency of such a “computing system? While existing digital computers do 109 operations per Joule, the “DNA computer” can do 2 · 1019 operations per Joule, which is 1010 more efficiently. The density of information in DNA is 1 bit / nm3, and in existing computers 1012 nm3 contains 1 bit. ”[50]? No. In this variant, under controlled conditions, a huge number of "DNA pathways" are generated spontaneously in parallel modes. Including the correct (optimal) ones. Further, the actual computing begins, but it is carried out by people. The intelligent isolation of DNA fractions is the process of obtaining a solution to the traveling salesman's problem. A person plays the role of a computer here, his mental participation is a condition for receiving an answer. In contrast, this is not a participation in DNA programming, which would bring such work closer to the well-known digital computing. DNA itself is already "programmed" for complementarity during the evolution of living systems. In these acts, a quick enumeration and finding the optimal wave vectors of self-organization of biosystems, the highest manifestation of which is morphogenesis, is achieved.
DNA Computing
A little more about Adleman's model, since his and our logics are fundamentally different. As we (and not only) believe, the path chosen by Adleman and his numerous followers, using DNA as a “computational” structure, is incorrectly assessed by them as a kind of DNA computing. David Gifford, one of the leading authorities in computing who first supported Adleman, said that "this is not a molecular computer" and that this technique "... can only solve some kinds of combinatorial problems, it is not a general-purpose or programmable computer like the IBM PC".
Thoughts About Logic
For each question, choose the best answer. The answer key is below.
- For how many years had the number theory been studied?
- For 2000 years
- For 3000 years
- With what field did the this theory collide?
- With biology
- With computering science
- How is called this unity?
- the diversity theory
- the complexity theory
Answer Key
- For 2000 years
- With computering science
- the complexity theory