This paper is the notes and summary of the course introduction to Computing and Basic Programming taught by Mr. Li Ge in the School of Information Technology, Peking University
Chinese university MOOC courses are really good, a good university has no walls makes people feel moved wow, hahaha.
PS: It’s not toha
Calculation of origin
Three mathematical crises to Godel’s incompleteness theorem, resulting in computable and uncomputable boundary problems. The exploration of boundary problem led to the appearance of Turing machine.
The First Mathematical crisis (Discovery of irrational numbers)
The story begins in 500 BC
Pythagorean school
Faith:
- Number is the origin of all things, and the nature of things is determined by a certain quantity relationship. All things constitute a harmonious order according to a certain proportion of quantity.
- All numbers can be expressed as integers or ratios of integers
Later, Pythagoras also proved the Pythagorean theorem, but at the same time found that “the ratio of three sides of some right triangles cannot be expressed by integers”, for various reasons, Pythagoras did not announce, hipparsus also discovered and announced it.
Hippasus paradox
Hipsos considered the question: what is the diagonal length of a square with sides of length 1?
- At that time, there was no concept of irrational number, and its diagonal “√2” naturally could not be expressed as the ratio of two whole numbers
- When Pythagoras’ other disciples learned of this, they killed Hippasus and threw him into the sea in order to maintain the legitimacy of the sect.
This is where the mathematical crisis begins.
The crisis eases
Two hundred years later, With the help of geometry, Eudoxus established a complete theory of ratio, which avoided the problem of irrational numbers
Crisis resolution
In the second half of the 19th century, after the establishment of the theory of real numbers, the nature of irrational numbers was thoroughly understood. The establishment of the legitimate status of irrational numbers in mathematics solved the first mathematical crisis completely and successfully.
The Second Mathematical crisis (Calculus)
Newton and Leibniz discovered calculus independently in the 17th century, but both based their theories on an analysis of infinitesimals.
Berkeley paradox
Infinitesimal in Newton’s theory"Now it's zero, now it's not zero." 
As we can see from the derivation of calculus, △x is not zero in the denominator, but is equal to zero in the final formula. The result of this contradiction is disastrous, and mathematicians have been unable to find a solution for a long time.
Crisis resolution
More than 100 years after the invention of calculus, the French mathematician Cauchy defined infinitesimally small quantities in terms of limits, and finally solved the problem.
The Third Mathematical Crisis (Set Theory)
Mathematicians have always had the dream of trying to establish some basic axioms and then using rigorous mathematical logic to derive and prove all the theorems of mathematics. After Cantor invented set theory, French scientist Poincare thought: we can use set theory to build the whole mathematical building.
Russell paradox.
S consists of all elements that are not themselves. Does S belong to S?
Russell’s Paradox is popularly described as a famous barber in a certain city who says, “I will shave everyone in my city who does not shave himself, and I will shave only them.” So who should shave your own face?
Crisis resolution
Mathematicians have worked so hard to build a mathematical building, but at last it is found that there are defects in the foundation, and mathematicians have put forward their own solutions. It was not until 1908 that the first axiomatic system of set theory was established that the defects of set theory were remedied.
Although the three mathematical crises have been solved, the impact on the history of mathematics is very profound. Mathematicians try to establish rigorous mathematical systems, but no matter how careful, there are flaws
Godel’s incompleteness theorem
In any mathematical system which is derived from finite axioms and basic concepts, and from which the system of natural numbers can be derived, a statement can be found which we can neither prove nor disprove
The first theorem,
Any formal system involving first-order predicate logic and elementary number theory has a statement in which it can be proved neither true nor false.
The second theorem
If the system S contains elementary number theory, when S is free of contradictions, its incompatibility cannot be proved in S.
Godel’s incompleteness theorem declares that it is impossible to formalize mathematics completely
Computable boundary problems
Although Godel’s incompleteness theorem declares that it is impossible to formalize mathematics completely. But we still want to be clear about what can be proved (calculated) and what can’t. This is a computable boundary problem
Mathematicians give the idea of research: establish a mathematical model for calculation, called a computational model, and then prove that any task that the computational model can accomplish is a computable task.
Alan proposed a model for this problem, a Turing machine
Turing and the Turing machine
Speaking of the Turing machine, one of the most memorable figures in the history of computing is Alan Turing
Turing
Look at the resume:
- He was born in London in June 1912
- During middle school, he was awarded the Gold shield of Mathematics by King Edward VI
- He was elected a fellow of King’s College, Cambridge in 1935
- In May 1936, Turing proposed the Turing machine, (published in the London Mathematical Society Proceedings)
- In 1938, he received his ph. D. degree from Princeton University
- Code-breaking work during World War II, 1938-1945 (served as general Adviser to the British and American Code-breaking Departments)
- He was awarded the British Empire Order in 1946
- In 1950, came up with the famous Turing Test.
- October 1950, published the paper “Can Machines think” (started the research of artificial intelligence)
- 1951 – Elected fellow of the Royal Society (fourth in his family)
- In 1952 Alan wrote a chess program
- He died in 1954
In 1936, in his famous paper “On the Application of Computable Numbers to decision problems”, Turing proposed a mathematical model of an ideal computing Machine, the Turing Machine.
Turing machine
Turing machine composition
Here’s a blurry but clear picture:
One memory tape
- Two-way infinite extension
- There are little squares on it
- Each square can store a number/letter
A controller
- Can store the current state of its own;
- Contains a read/write header that reads, writes, and changes the numbers/letters on each row of the tape
- You can change your state according to the letters/numbers you read
- You can go along the tape
The working steps of a Turing machine
- Preparation:
- Memory initializes with a sign;
- The controller sets its current state;
- Read/write head in starting position;
- Prepare working procedures;
- Repeat the following until shutdown:
- Read/write headers read letters/numbers from the current grid on the memory strip;
- According to their current state and read the character, find the corresponding program statement;
- According to the corresponding program statement, do three actions:
- Writes a corresponding letter/number to the current memory strip square;
- Change its state to a new state;
- The read-write head moves one step to the left or right;
Theoretical significance of Turing machine
-
Computability determination:
Given A sequence of symbols A, the passage from A to B is computable if A Turing machine can be found to give the corresponding sequence of symbols B.
-
A general computing model that can be realized is given.
-
The idea of operation through “read-write symbols” and “state changes” was introduced;
-
Demonstrated the ability to perform complex operations based on a simple alphabet;
-
Introduced the prototype of storage area, program, controller and other concepts;
Why can a computer calculate?
We all know that numbers in a computer are represented in binary, so how does a computer do it?
So let’s start with a little bit of background Boolean algebra
Boolean algebra
In 1854, G Boole published “A Study of the Laws of Thought — Mathematical Theoretical Basis of Logic and Probability”, and integrated his other article “Mathematical Analysis of Logic”, founded a new subject – Boolean algebra. It provides an important mathematical method and theoretical basis for computer switch circuit design.
Logical operation method
Logic and
Circuit diagram:
Function expression: F = A * B
Truth table:
| A | B | =F |
|---|---|---|
| 0 | 0 | = 0 |
| 0 | 1 | = 0 |
| 1 | 0 | = 0 |
| 1 | 1 | = 1 |
Logic or
Circuit diagram:
Function expression: F = A + B
Truth table:
| A | B | =F |
|---|---|---|
| 0 | 0 | = 0 |
| 0 | 1 | = 1 |
| 1 | 0 | = 1 |
| 1 | 1 | = 1 |
Logic is not
Circuit diagram:
Truth table:
| A | =F |
|---|---|
| 0 | = 1 |
| 1 | = 0 |
With or
- Both numbers are equal to “1”.
- The two numbers differ by “0”
Exclusive or
- Both numbers are equal to “0”.
- Two different numbers are “1”
calculation
Conventional calculation method
For example, if A=0b1101, B=0b1001, find A+B.
In conventional calculation, it looks like this:
The way a computer calculates
Let’s look at the lower half adder
Through the combination of several half adder, we can get the full adder
Again: Why can computers calculate?
Knowing this, we can answer the question:
- First, number operations can be converted
A binary numberCalculations; Binary operationCan be converted to basicBoolean operation;- The basic
Boolean operationCan be bycircuitComplete; - A computer is made up of these basic circuits
So computers have computing power.
A little more technical descriptionALU
The Boolean operation and computation method we described above are the two core units of the COMPUTER ALU:
A logical unit: Performs logical operations, such as and, or, and notThe arithmetic unit: Responsible for all digital operations in the computer
In this case, use Java to simulate the implementation of a full adder!
Adder implementation
Take a look at the next diagram:
Code examples:
public class ALU {
/** ** half adder **@paramA to be added star@paramB to be added star@returnHalf plus standard and carry */
public int[] halfAdder(int a, int b) {
int carry;
int sum;
sum = XOR(a, b);
carry = AND(a, b);
return new int[]{sum, carry};
}
/** ** full adder **@paramA to be added star@paramB to be added star@paramC Number of digits to be carried *@returnStandard and carry */ after full addition
public int[] fullAdder(int a, int b, int c) {
int carry;
int sum;
int[] first = halfAdder(a, b);
int[] second = halfAdder(first[0], c);
sum = second[0];
carry = OR(second[1], first[1]);
return new int[]{sum, carry};
}
/** * xor operation */
public int XOR(int a, int b) {
return a ^ b;
}
/** * and the operation */
public int AND(int a, int b) {
return a & b;
}
/** * or operation */
public int OR(int a, int b) {
return a | b;
}
/** * 8 bit adder, step by step version **@paramBinaryA Binary array *@paramBinaryB Binary array *@returnBinary * /
public int[] FullAdder_8_Bit(int[] binaryA, int[] binaryB) {
int[] out = new int[8];
int[] first = halfAdder(binaryA[7], binaryB[7]);
out[7] = first[0];
int[] second = fullAdder(binaryA[6], binaryB[6], first[1]);
out[6] = second[0];
int[] three = fullAdder(binaryA[5], binaryB[5], second[1]);
out[5] = three[0];
int[] four = fullAdder(binaryA[4], binaryB[4], three[1]);
out[4] = four[0];
int[] five = fullAdder(binaryA[3], binaryB[3], four[1]);
out[3] = five[0];
int[] six = fullAdder(binaryA[2], binaryB[2], five[1]);
out[2] = six[0];
int[] seven = fullAdder(binaryA[1], binaryB[1], six[1]);
out[1] = seven[0];
out[0] = seven[1];
System.out.println(Arrays.toString(out));
return out;
}
/** * Optimized version, custom adder length **@paramBinaryA to be added *@paramBinaryB Group to be added *@paramBitLen Operation length *@returnThe calculated array length */
public int[] FullAdderBits(int[] binaryA, int[] binaryB, int bitLen) {
int[] out = new int[bitLen];
int[] tmpRes;
int[] first = halfAdder(binaryA[7], binaryB[7]);
out[bitLen - 1] = first[0];
tmpRes = first;
for (int i = bitLen - 1; i > 0; i--) {
tmpRes = fullAdder(binaryA[i], binaryB[i], tmpRes[1]);
out[i] = tmpRes[0];
}
out[0] = tmpRes[1];
System.out.println(Arrays.toString(out));
return out;
}
public static void main(String[] args) {
ALU alu = new ALU();
// {high ----------- low}
int[] a = new int[] {0.1.1.1.0.0.1.0};/ / 114
int[] b = new int[] {0.0.1.1.0.0.1.1};/ / 51
alu.FullAdder_8_Bit(a, b);
alu.FullAdderBits(a, b, 8); }}Copy the codeLet’s look at the test output:
(1, 0, 1, 0, 0, 1, 0, 1] / / 165 [1, 0, 1, 0, 0, 1, 0, 1] / / 165Copy the codeThere is no +, –, *, / (ignore the for loop!) , completely through logical operations.