25 May 2007
It was under the guiding light of the Gödel Incompleteness Theorem that I sought a missing axiom that might lead to the resolution of the problem of creating a GENERAL formula for Primes. This must work for ALL primes.
Having created the Pythagorean Perimeters Theorem, by which a perfect rectangle of Diophantine ratio converts to a Diophantine right triangle (Pythagorean triangle) of the same perimeter, I noticed that this was creating NEW PRIMES.
Explanation: If the ratio of the perfect rectangle is coprime, a new prime must have been created, because a Pythagorean BASE TRIPLE (eg 3:4:5 but not 6:8:10) is always coprime. So a coprime DUPLE becomes a coprime TRIPLE, and somewhere the mathematics is generating a prime.
This I called the "neogenesis of primes".
My first approach was destroyed, amidst the background bickering for which sci.math is notorious, by somebody who gave his Internet handle as "Quasi".
If A and B are coprime, A with B and with (A+B) are also coprime. A coprime duple is converted to a coprime triple even by the simple arithmetical function of addition.
This is an excellent example of the mathematical principle of "couterexample" because of its simplicity.
I continued to think publicly when I proved the corollary that the principle of the "neogenesis of primes" is also contained within subtraction. The proof is trivial because addition and subtraction are "mirror-image twins" containing the same axioms.
So the "neogenesis of primes" is contained within arithmetic itself, and does not need to be "imported" from geometry to compensate for one of the missing axioms.
Having been helped to leave an unfruitful path of logic, I examined
the way in which primes can initially be selected by the 6n plus-or-
minus 1 algorithm. This gives ALL primes, but some "false primes" like
25, 35 and 49. Can arithmetic decide to remove the "false primes".
I was thinking in a Hilbert way (more on this later). I wrote "ARITHMETIC CANNOT DECIDE".
After "thinking in public" further, I corrected my statement. I was thinking in a Turing way (more on this later) and wrote "ARITHMETIC CAN DECIDE".
I mentioned the Hilbert Decidability Problem (German - "Entscheidungsproblematik"), and decided to investigate.
Dr. Yuri Matiyasevich of St. Petersburg, Russia gave an perfectly clear account of Turing's response to the Hilbert problem, excellently translated into English, here: http://logic.pdmi.ras.ru/~yumat/H10Pbook/par_5_7.htm
If that is missing from the Web, I have copied it here:
A HREF=http://www.wehner.org/primes/par_5_7.htm
I was given permission to do this, if I recognise Yuri Matiyasevich
as author and The MIT Press as publisher, and include the following link:
http://mitpress.mit.edu/9780262132954/
They were researching the parameters of a future "computing engine",
and Turing suggested that a box might have a "ticker-tape" such as was
used for stock-market reports at the time. This one-dimensional array
is a paradigm that imitates the one-dimensional array of RAM in a
modern computer, so that a "Turing Machine" is not an obsolete model.
Hilbert had required that M n-tuples be selected by some test, in order that two lists be created. One is a list of those that pass the test, which might be at address 123 (or whatever), and another is a list of those that fail the test, such at address 0.
Notice that a "Turing Machine" has "random access" (a misnomer,
because neither 0 nor 123 is random, but the way in which the machine
toggles from one list to another seems arbitrary because it depends on
the "decision" of the test).
My own concept of "to decide" proved to be intimately bound up with
this, because I was looking upon the Turing box as a kind of toolbox,
where the tools inside are arithmetic and logic, and the axioms
thereof influence the outside behaviour of the box.
George Boole had taken the concept of arithmetic, such as the addition, and used it as a generator of logical OR.
Arithmetic (addition):
1 + 1 = 2 1 + 0 = 1 0 + 1 = 1 0 + 0 = 0 |
Here, in positive logic, zero is "false" whilst any other number (a Diophantine) is "true".
It may have been simply to stop the 1s and 2s looking like numbers that he decided to standardise the value of "true":
Logic (or):
1 + 1 = 1 1 + 0 = 1 0 + 1 = 1 0 + 0 = 0 |
However, the result had wider implications than mere tidiness.
Given a Turing Machine, we can use arithmetic to find the "0". So the
output of the arithmetic is a Diophantine or zero. This we multiply by
123.
Those that fail the test are delivered to the list at address 0. They are all together. So arithmetic CAN decide a zero.
Those that pass the test return from the arithmetic with any Diophantine. So they "spray" the results into locations 1*123, 2 *123, 3 * 123 and other places. The results that pass the test are therefore not kept together in a single list, but scattered arbitrarily in the RAM at intervals of 123. These will be addresses 123, 246, 369 and infinitely more possible locations. So arithmetic CANNOT make a second clear decision.
This is the TURING SEMI-DECIDABILITY principle, and also an example of the Gödel INCOMPLETENESS of axioms. Half of the "decidability" is missing.
However, if we had carried out some BOOLEAN process upon the
arithmetical result, prior to the computation of the list address, the
Boolean result would have given only 0 and 1. When multiplied by 123,
it would have given zero and 123 for the two lists. Of course, one can
add a constant, and get 100 and 223, or any other two list-addresses.
The important point is that it TOGGLES between two addresses. This is
Hilbert (full) decidability. Arithmetic cannot do this.
We can create the COMPLEMENTARY arithmetical formula for the above
test. It would be a test for non-primes, for example, instead of for
primes. In such a case, zero would mean "false - it is NOT non-prime".
So we would get 0 for primes.
We could subtract this from 123, and it would land at exactly the same
list-address (zero) where the non-primes are listed, at 123.
However, when this complementary Turing semi-decidability is used to get a "true", we get 123 minus 123 sometimes (a correct address), and -123 or -246 on other occasions. The Turing complement is still semi- decidable.
So the first arithmetical test has a one-word vocabulary "NO". In the second case, we asked the question backwards and got a "NO" which means a "YES" to the first question.
One test can only say "NO". The other can only say "YES". How do we link the two semi-decidables?
The ONLY way is by means of a Hilbert decidable, which understands BOTH words and can interpret between them. Only a Boolean function can do this.
Conclusion so far:
Arithmetic is "Turingian".
Boolean logic, or arithmetic with Boolean, is "Hilbertian".
Further point:
An example of the Gödel incompleteness of an axiomatic system is seen
here in the arithmetic, where half its deciding power is missing.
And now, to the primes:
We consider the "Sieve of Eratosthenes", but carefully because we are examining its "decidability" properties.
The "True" word of our logic will be called "Accept", in that we accept the number as prime. The "False" word of our logic will be called "Reject" in that we reject it even when it was previously accepted.
Can we "sieve" the primes with a one-word logic?
We "Accept" all the Diophantines.
However, to be generous we retract that statement. Let us say that the Diophantines are given.
We plan to "Reject" the non-primes with a "sieve".
Where do we start?
We can start at 4 and add 2 to land on the next even. Then we go on to the 8, 10 and so on. We sieve out all evens and are left with odds, other than 2.
What do we sieve out next?
We need to create a list of primes. A factor can only be a factor if it is BELOW the number of which it is a factor.
We could go to 3, and see if multiples of 2 land upon it. This is trivial, because everything is odd.
Then we could go to the 4, and see if the PREVIOUS LIST of primes divides into it.
Then we could go into the 5, and check the previous list of primes.
And so on. We are just REJECTING those that have factors.
However, at the start, there is NO PREVIOUS LIST.
To start, we have to ACCEPT the 2 into the primes list. Only then can the 3 be found and put into the list, and then the 5 and then the 7.
There are no primes below the 2, so it cannot be obtained from the number-line by rejecting others around it. It is an AXIOM that 2 is prime - not the result of a "sieving" action but because of "common- sense" outside of the "Sieve of Eratosthenes" algorithm.
Such a prime, upon being accepted into the list, requires the availability not only of "Reject" but also of "Accept".
So the problem of Primes is "Hilbertian".
A "Turingian" system like arithmetic CANNOT generate a general formula for primes, valid to infinity.
CONCLUSION:
If a claim is made that a "formula" gives ALL the primes to infinity, it must be checked for the presence of at least one single Boolean construct. If such a thing as AND, and NAND, and OR, and NOR, and XOR, and XNOR, and NOT, and "IF" and "BOOLEAN" and every other Boolean is missing, then the formula will always break down. It will not deliver all primes.
There are very good approximations, however, that deliver many.
I conceived the word "BOOLEAN" because it is easily implemented on a computer. It may already exist.
In Basic, Pascal or similar:
(Arithmetical, or Turning semi-decidable side) |
In Pentium code, the number in EAX:
;;; (Arithmetical, or Turning semi-decidable side)
and eax,eax ;;; Make eax set or reset the zero flag
jz Hilbert ;;; Zero stays zero
mov eax,1 ;;; Diophantine overwritten by 1
Hilbert:
;;; (Logical, or Hilbert decidable side).
|
It only takes a single Hilbert construct to import the missing half of the "decidability" into the arithmetic. Such an arithmetic, that has some logic added, I dubbed a "logical transarithmetic".
Arithmetic cannot solve the primes problem. Only a logically-augmented arithmetic - a logical transarithmetic - can.
Charles Douglas Wehner
| HOME |
(C) 2007 Charles Douglas
Wehner.
Use freely but do not plagiarise.
If, however, the "comb" is just a single tine (tooth), when inserted at position twice zero, it would "comb out" zero. Ergo, zero cannot be prime.
But what about the notion that one is prime? We have a comb of unit pitch,
inserted at position 2.
It can be seen that if one is prime, it is the ONLY prime number. Arithmetic cannot see the absurdity of this, but human intellect can. It is on this basis, that we move on to the number two. It is legal to remove the one explicitly, because our algorithm allows removals.
So far, we have not used the "comb". We have considered doing so, but would havee "combed out" the zero, and then ALL numbers, and so have decided not to start "combing" yet.
When we moved on to the two, we inserted the "comb" of pitch two at position FOUR. Thus, we have leaped over the numbers two and three. These were not tested. See the earlier diagram. By starting the "sieve" process at four, we have "accepted" the two and the three. Purists may say we have "half combed" the three, because although we hav not removed anything below it by "combing", at least we have removed the four.
To be properly tested, a number must start to the right of all the combs, and must end up to the left of them, as the "sieve" algorithm follows the sloping green line in the diagram above. The two and three are exceptions. Therefore, they have been "accepted" by human decision-making and not by the "sieve" algorithm.
No matter how the problem is re-formulated, this "exception handling" will always reappear, because it is built into the axioms of primes. In other versions, the "exceptions" are scattered along the number line all the way to infinity.
The study of Hilbert "Decidability" and Turing "Semi-decidability" led to the decision being made to incorporate not just an arithmetic unit (AU) but an arithmetic and logic unit (ALU) into modern general-purpose computers. The prime problem is Hilbert soluble, and the machinery is available.
Modern computers therefore have greater power than required by most of their mathematical applications.
| HOME |