Drashing from the specific process of solving the problem, only by describing the function required to describe the required program, so that the computer can generate the problem with the problem, which is undoubtedly an inevitable direction of computer programming. I will call it automatic programming below. I have seen a few articles on computer automatic programming in 9CBS, and put forward some ideas, but they always leave, that is, computer automatic programming is to build strong computing power in the future computer, because it Many or less to contact artificial intelligence. Such a future is really frustrating, because I know that the computer seems to have a "smart" shadow, even if there is anything? What is its efficiency? Will it inherit the defect of human wisdom? For example, will it also have bugs? But carefully analyze this problem, the prospect may be not so bleak. Let's go back to the first paragraph: By making the function you need to meet the function you need to make your computer you generate a solution to the problem. It seems that computer automatic programming needs two major issues: one is how to build a language, use it to describe the functionality of the program. This language is preferably higher than the current programming language, as it does not describe the specific process of solving the problem, we may wish to call it "functional" language. The second is how to let the computer find a solution to the problem. This is undoubtedly the most important issue, and we are going to explore this. The language in the first question is to completely replace existing languages - almost all issues can be used to obtain their solve algorithms in a programming approach, and natural is exhaustive (of course, there are exceptions, such as output only one bit) The algorithm is not linen). We can write a solution algorithm for a problem without effort, this algorithm already contains all the description to implement functionality. The next step is how to convert this stupid algorithm into a low-time complexity algorithm. At this point, the second question is converted to: How to calculate the algorithm? Perhaps it can be said that this problem solves the problem of computer automatic programming.
Each algorithm can implement a function, although it may be a function of processing a string, we can use encoding to define the domain / value domain to map Nature set N. In other words, the functions implemented by each algorithm can be represented by a number theory function. In this way, the algorithm is simplified, in fact, it is to scale the corresponding function. To achieve algorithm, it is inevitable that the rules of the transformation between a series of algorithms (the algorithm here must be the same function, we will be called an equivalent algorithm), which is similar to mathematical operational law, and the fact On, the operational law in mathematics is also from this set of rules. Then we can ask a lot of questions, such as this is a very simple rule? Can any algorithm be converted to its rule of any equivalent algorithm? Is it all algorithms?
Let's first look at the second question: Does any algorithm can transform the rules of any equivalent algorithm?
For each proof issue, it can be seen as a nature of all elements that determine a collection. Further, prove that a proposition is to process a function f (x) defined on a set X, see if it outputs all of the inputs 1. If we put the calculation of this f (x) algorithm, what will it be? Undoubtedly, this algorithm is the simplest equivalent algorithm only one: Return 1. This shows that algorithm simplicity simplicity is certified. There is a new problem here: according to the Naddel's incomplete theorem, there is such a proposition, it is really true, but you can't prove it for it. The problem is, if it is fixed, how is the corresponding f, what is the result? If you want to achieve the simplest, isn't it to never get the result? In this way, we have concluded that any algorithm can be converted to its any equivalent algorithm, because such a set of transform rules do not exist.
The reason is apparent, the algorithm of calculating F (X) mentioned above is equivalent to returnit, but both cannot transform each other.
In the third question, we can guess by chaos.
A simple function that often generates unpredictable behavior through iteration. For example, insect model:
XN 1 = kxn (1-xn)
This equation seems simple, but it can produce extremely complex behavior. For example, when k is more than 3.5699, if a coordinate system is established in N is the X-axis, X is the Y-axis, and the X value obtained each iterate is drawn, you will find that the change of X is almost millions There is no regular, in other words, its performance is almost different from a random variable, which is chaos. Chaos is in reality. The same phenomenon also occurs in the Cell Automobile (CA).
Here is a reference:
After 256 primary CAs and other more complex CAs, Wolfram found that CA can be divided into four categories. The mathematician and writer Rudy Rucker describes these four types in its report "Things Computer Science Tells US About Philosophy" (see Referring).
Category 1: Constant. (All seeds are "dead") Category 2: Repeat. (Cycle, strip) No. 2A: Nested. (Regular Fractal) Category 3: (Pseudo) Random. (激变) Category 4: Complex. ("Irregular". Telling. General calculation)
Wolfram has made a seemingly stateable statement, most of the Class 3 and Category 4 CA may not be omitted (Computational Irreducible): give an initial state, to find a certain cell in the nth step, All N step calculations must be completed from the initial configuration. That is, there is no formula or shortcut to predict the future of CA.
Here, the 3rd, 4 class CA is obviously chaos. It is worth noting that the last sentence, at this time, "there is no formula or shortcut to predict the future state of CA". This also means that if we use the algorithm to represent the function relationship between X and N, it is possible to expect to use algorithm to simplify to a simple algorithm, the only way to predict the future state is the calculation of step by step. Of course, this should be just a guess of Wolfram, not strictly proven, intuitive, my rightness, the correctness of this point is no doubt, interested friends can try to prove. In fact, the meaning of these two issues is just to let us see some of the clues of algorithm, let us understand its capacity limit. They don't mean that the algorithm is simple, because after all, in practical applications, they rarely meet the above.
Here are some questions. The Codel Unstoppable Theorem is said: Any compatible mathematical formalization theory, as long as it is sufficient to define the concept of natural numbers, it can be constructed in the system in the system. Whether ordered proposition.
This theorem does not mean that any axiom system is incomplete, such as Europide geometry can be accessed into a complete system. In fact, the computer proof of the geometric issue has been resolved, which inspires our ambition, seeking a small amount of fractive rules, may have a good result.
