Turing machine does not specifically refer to a certain machine or type of machine, but a concept defined in the language of mathematics. It is a tool invented to answer the ultimate questions of mathematics by mathematicians in the 20th century. Its purpose
It is to abstract and simplify the complex mathematical activities in the human mind.
Seven sets are required to define a Turing machine. The two most important ones are "the set of finite non-empty states (State)" and "the set of finite non-empty symbols (Symbol)". The former represents "this machine can
The types of symbols read and written on the paper tape" are also called "color numbers". The latter represents "the states that can occur inside the machine" and are called "state numbers" - which can be easily understood
It means "the machine can open the first and second gears".
The remaining five include "blank symbol", "initial input symbol", "initial state", "transition function set", and the special "stop state", that is, "the machine must stop after entering this state."
As long as these seven elements are present, a machine can be a Turing machine.
In fact, when the great mathematician Alan Turing created this concept, he did not design a machine that could actually run it. It was many years later that von Neumann created an engineering implementation of a Turing machine based on electricity.
For example, the abacus is divided into upper and lower sides by a beam. The two upper beads, whether they pass through the beam or not, can be used to express three symbols from 0 to 2. The five lower beads, whether they pass the beam or not, can be used to express
It represents six states from 0 to 5. The abacus can be regarded as a machine with three colors and six states.
At this time, if a mathematician writes down all the transfer functions corresponding to the three colors and six states on paper, and trains a person (or monkey) to move the abacus strictly according to the set of transfer functions, then the abacus and the user will
It can be regarded as "a Turing machine".
Yawgmoth vaguely remembered that many years ago, he seemed to have done similar research with Xiang Shan. DNA was regarded as the "paper tape" of the Turing machine, the four base pairs of DNA were regarded as "a collection of symbols", and
Amino acids are regarded as "states", and ribosomes and mRNA have "transfer function sets"...
The cell nucleus of eukaryotes on Earth may be a four-color N-state Turing machine.
Among the many Turing machines, one called the "Beaver Machine" is the most outrageous.
BB(n), BB means "Busy Beaver", busy beaver. It is a terminating program that looks for the maximum output that can be generated after given parameters. The simplest two-color two-state beaver machine only has "open and
Off" two states, and can only output "0 or 1", and will stop when outputting 1. The two-color two-state beaver machine can output 4 1's through 6 state transitions, so BB(2)=6.
BB(3)=21.
BB(4)=107.
However, humans have not yet enumerated all 5-state Beaver Turing machines. We only know that BB(5) is either 47,176,870, or it is greater than 10 raised to the eleventh power.
BB(6) has been determined to be greater than 7.4*10^.
In 2016, a mathematician encoded Goldbach's conjecture into a 43-state beaver machine. The coding logic is very simple, which is to verify every even number from small to large. If it is found that an even number can be expressed as one of two prime numbers
and , then examine the next even number. As long as this Turing machine completes BB(43) steps and does not stop before finishing, then humans can conclude that it will never stop, so Goldbach's conjecture is true.
But the problem is that the universe has less than 10^80 atoms. This number is even much smaller than BB(6), let alone BB(43).
Yawgmoth was amazed at how outrageous this idea was. The matter and energy in the entire universe cannot support this level of calculation. If you want to record the specific value of this number, you have to record the ratio on every atom in the universe.
There are too many digits in the number of atoms in the universe. This is an uncalculable value.
"But even so, this is still the pursuit of 'infinity' in the 'finite' step." Xiang Shan introduced it this way, "If we use a more banal way to exhaust all even numbers, then
The matter and energy we need are 'infinite'. Rational numbers are an infinite concept. This method can only be used when Goldbach's conjecture is false - that is, a Goldbach has been found in infinity.
A counterexample to the conjecture. But BB(43), although it is larger than the universe, is a finite number. The Beaver machine completed the exploration of infinity through finite steps in a finite time."
"But what's even better is that humans can actually find better ways to prove Goldbach's conjecture - the final proof only consumes a little bit of the light and heat from the sun. You see, the effect of wisdom is
How terrible."
The energy that nourished all mathematicians from Pythagoras to Anatole was a small amount of energy released by the sun, solidified by plants, and transformed by animals. Compared with the universe, it is insignificant.
But this tiny bit of energy has solved many answers that would be difficult to obtain even if the universe were burned.
Yawgmoth nodded. But then he thought of another question.
——Anatole completed it in his 20s...
…
"Compared with 'exhaustive infinity', the efficiency of BB(43) is horribly high, isn't it? But what's even more horrifying is that humans can find more efficient paths leading to answers to problems." Xiang Shan raised the question.
Wine glass: "To our great minds."
Yawgmoth nodded. He still remembered that his best friend's long-cherished wish was to understand "why the power of wisdom can be so efficient."
What exactly is wisdom to this universe?
Yawgmoth felt his passion rekindled. He was inspired by his best friend's words and thought of his dream again.
In a daze, he had finished his meal and walked back to his research room.
"It's true that there has been a bit..." Yawgmoth pressed his head. For him, "scientific research" is a comfort zone. He seems to have closed himself in this zone for a long time, dealing with various issues every day.
He was so busy doing biological research that he forgot everything else. This kind of thing was a drain on his mind.
Fortunately, Xiangshan is here.
But at the door of the research room, Ingrid stopped him.
"Hey, Yog." Ingrid said to him.
Yawgmoth felt a trance. He vaguely remembered that Yingjia seemed to have too much respect for Xiangshan recently... But another memory told him that an East Asian specialty party game called "King's Game" was popular in the company recently...
——Is Xiangshan someone who knows how to play this kind of game...
——No, Yingjia has finished her meal? So quickly?
"Do you still remember the research we, you, me, Xiangshan, your ex-wife, we did on the Rama Project?" Ingrid asked, "Think of DNA as a 'paper tape' and ribosomes as a 'magnetic head'
', mRNA is regarded as a register that stores the state of the machine. Amino acids are a set of states, and the DNA code table is temporarily regarded as an instruction list... When conducting scientific research, it is the only time you are allowed to 'doubt', so remember my tips for you first.