Current location - Education and Training Encyclopedia - Graduation thesis - Two problem in discrete mathematics
Two problem in discrete mathematics
Computational theory can be traced back to 1900, when the famous mathematician Hilbert gave it at the mathematician conference at the turn of the century.

The international mathematical community has put forward 23 famous mathematical problems. The tenth question is: Is there a limited,

Can mechanical steps judge whether Diophantine equation has a solution? Here, limited and mechanical proof steps are proposed.

The problem, in today's words, is the algorithm. But people didn't know what "algorithm" was at that time. In fact, at that time,

Many problems in the field of mathematics are closely related to "algorithm", so it is called the scientific definition of "algorithm".

Want to go out. Later, in the 1930s, two people finally put forward a method to define the algorithm accurately. One is

Turing, a person is the church. Among them, the Turing machine model proposed by Turing is intuitive, so it quickly got everyone's enthusiasm.

Accept it all.

I don't know if you have heard of the name Turing. Maybe some people know Newton, Einstein and even Feng.

Neumann, but I don't know Turing. However, Turing's contribution is absolutely no less than these masters of science. Turing's greatest contribution is to put

His Turing machine model clearly explains the basic and profound concepts of the algorithm. It is precisely because of Turing's theoretical basis.

Only in this way can people invent the greatest invention since the 20th century, even in human history: the computer. So people

Turing was called the father of computer theory.

Turing lived in the era of World War II. He worked for the British government during World War II and successfully deciphered it.

German cipher has made outstanding contributions to Britain. In fact, it was because of World War II that the British government was willing to pay Turing.

To be the most primitive computer, of course, this kind of computer is specially used to crack passwords, not everything we use now.

computer. (There is a movie called Cryptography, and the English name is "enigma", which is based on Turing's deciphering of the German code at that time.

Adapted from a story, you can look for it if you are interested. )

Turing is a strange man, who only likes to study hard by himself and doesn't like to communicate with others. It is said that he is still

A homosexual. You know, in Britain at that time, homosexuality was a big illegal act. Finally, at the beginning of his career.

He committed suicide when the wind blew towards him. In order to commemorate this great scholar, the computer industry has set up the highest honor award: ACM.

Turing Award.

On the one hand, the emergence of Turing machine laid the foundation of modern digital computer (you know, von Neumann was later based on Turing).

The idea of designing the first computer). On the other hand, according to the basic concise concept of Turing machine, we can also

See what the calculable limit is. In other words, in fact, the ability of computers is limited in principle. Please note,

When I say the limit of a computer, I don't mean that it can't eat, can't sweep the floor and other hardware limits, just from the information office.

From this perspective, computers still have their limitations. This is the downtime of Turing machine. This problem is more in Turing's view.

More importantly, in his thesis, in fact, in order to demonstrate the Turing downtime problem, he proposed the Turing machine model "manually".

Type.

When it comes to Turing downtime, we can't help but mention Godel's theorem, Russell's paradox, Cantor's set theory and so on.

Wait for a series of big events. As early as the end of 19, Cantor made a basic research on set theory. You know, count.

Although learning is varied, it is found that all mathematics can be summarized by the concept of set, that is to say, set is

The foundation of all mathematics. Therefore, if we lay an axiomatic foundation for set theory, it is equivalent to laying a foundation for mathematics. healthy

Thor made this contribution. In addition, in order to prove the conclusion that there are more real numbers than natural numbers, he invented a

A proof method called diagonal deletion. Unexpectedly, the influence of this method is very deep and wide, until the later figure.

Stop problem and Godel theorem are actually different extensions of this method.

At the end of 19, people are busy building a mathematical axiom system based on set theory. However, just as this building is about to

When it was finished, something terrible happened. Russell paradox shattered the mathematician's dream. About Luo

A popular version of the vegetarian paradox is: "There is a barber in the village, and he made a rule for himself:' Don't give those places.

Others cut their own hair. Now, should this barber cut his own hair? "。 If you try to answer

This question will find something strange: the question itself seems impossible! Because of this strange logic,

The philosopher Russell subverted the foundation of the whole mathematics building!

Are you satisfied with the above answers?