Simple Geometry, Deep Math - Comments

[trilobite]

trilobite submitted a new PF Insights post

Simple Geometry, Deep Math

Continue reading the Original PF Insights Post.

 

[Robert Smart]

We should perhaps mention the boundary between computable numbers (includes e and pi) and non-computable numbers. Since there are only a countable number of computable numbers there are much more non-computable numbers. The Mathematics you get into with this is near the boundary with Philosophy. To me the non-computable numbers don't exist [disagree: show me one]. However they give us a model of the real line that is logically consistent and helps us to think clearly about it.

 

[trilobite]

We should perhaps mention the boundary between computable numbers (includes e and pi) and non-computable numbers. Since there are only a countable number of computable numbers there are much more non-computable numbers. The Mathematics you get into with this is near the boundary with Philosophy. To me the non-computable numbers don't exist [disagree: show me one]. However they give us a model of the real line that is logically consistent and helps us to think clearly about it.

Yes, that's a fascinating topic! Thanks for mentioning it.

 

[Jimster41]

care to explain a bit what the def of a non-computable number is?

 

[trilobite]

care to explain a bit what the def of a non-computable number is?

I believe that a computable number is one that can be computed to any desired number of decimal places by a finite number of operations. Usually, this is expressed in terms of a computer program that accomplishes the required calculation. The interesting thing is that the computable numbers are countable, essentially (I think) because there are only a countable number of computer programs. Since the real numbers are uncountable, this means that not only do non-computable numbers exist, but that "most" numbers are non-computable! However, as with transcendentals, actually exhibiting a non-computable number is not easy.

I hope that is an accurate and understandable answer. Robert, can you confirm (or correct) this explanation?

 

[SSequence]

I believe that a computable number is one that can be computed to any desired number of decimal places by a finite number of operations. Usually, this is expressed in terms of a computer program that accomplishes the required calculation. The interesting thing is that the computable numbers are countable, essentially (I think) because there are only a countable number of computer programs. Since the real numbers are uncountable, this means that not only do non-computable numbers exist, but that "most" numbers are non-computable! However, as with transcendentals, actually exhibiting a non-computable number is not easy.

Assuming LEM and assuming that decimal representation for real numbers is used, whatever you have written should be correct.

However, it is not quite clear what you meant with the last sentence though. It is quite easy to demonstrate specific examples of uncomputable real numbers. Of course just given a description it might not be easy at all to show that the given real number is uncomputable (and this is perhaps what you meant).

-----

The category of algebraic/transcendental numbers seems to be an interesting one. What is the simplest (and also precise) definition of algebraic numbers?

 

[trilobite]

However, it is not quite clear what you meant with the last sentence though. It is quite easy to demonstrate specific examples of uncomputable real numbers. Of course just given a description it might not be easy at all to show that the given real number is uncomputable (and this is perhaps what you meant).

I guess I meant "not easily understandable." But this is not an area I know a whole lot about. I would be interested to see an easily understandable non-computable number, if you have an example.

The category of algebraic/transcendental numbers seems to be an interesting one. What is the simplest (and also precise) definition of algebraic numbers?

The standard definition is that a number is algebraic if it is the root of a polynomial with rational coefficients. However, this wording was not very useful for the purposes of my article, so I chose a slightly different description.

 

[SSequence]

I guess I meant "not easily understandable." But this is not an area I know a whole lot about. I would be interested to see an easily understandable non-computable number, if you have an example.

Well there are many examples that one can easily give of course. I should perhaps describe a few that are more instructive.

The main elementary idea is that the set of all programs can be seen as a decidable subset of strings generated from a limited set of symbols say S (for example keys on keyboard or any other well-chosen finite set). The main condition is that S must have a finite number of symbols in it. For example, a typical example of S (for a typical limited programming language) could be:
S={ A--Z, a--z, 0--9, +, -, *, =, ; , ( , ) , { , } }
Possibly some symbols for space or endline could also be included (but that probably shouldn't be necessary as long as we have a marker for end of command).

One then, for example, considers a kind of 1-1 correspondence*** function between the set of strings (formed using symbols of S) that form valid programs and the set of natural numbers N={0,1,2,3,4,5,...}. The number that is assigned to each program is called its index.

Now think of a limited programming language that just takes one or more integers as inputs and gives a single integer as output.

Now here are number of examples of uncomputable real numbers:
(1) 0. h(0) h(1) h(2) h(3) h(4) h(5) ...
That is an uncomputable real number whose digit at n-th decimal place (assuming the counting starts from 0) is equal to h(n). Here we have h:N→N as:
h(x) = H(x,x)

where H:N x N→N is defined as:
H(x,y) = Given a program whose index is x and to which input given is the single integer y return 1 if the program eventually halts and 0 if it runs forever

(Well you could think of a minor complication when the program corresponding to index x takes more than one input. In that case you could simply think all other arguments, except the first one, as 0. Generally speaking, these kind of minor variations quite often turn out to be inconsequential).

(2) There are large number of ways of defining a pairing function from N x N → N. For example, one simple way is:
https://en.wikipedia.org/wiki/Pairing_function

So suppose we have a function pair:N x N →N (such as one described in the link above). Define A:N→N and B:N→N as functions that return the first and second coordinates for a value that is paired (described by variables x and y respectively in the link above). For example:
A( pair(3,5) ) = 3
B( pair(3,5) ) = 5
etc.

We have as second example of an uncomputable real number:
0. H( A(0), B(0) ) H( A(1), B(1) ) H( A(2), B(2) ) ...
That is at n-th decimal place we have the digit H( A(n), B(n) ).

(3) Suppose we have a total function F:N x N → N that lists all total recursive functions of one variable (that is, each "row" of this function F is a total recursive function(of one variable) and furthermore every total recursive function occurs at least once in some row). Note that F is not a (total) computable/recursive function****.

Now define a function g:N→N such that:
g(x)=0 whenever F(x,x) is non-zero
g(x)=1 whenever F(x,x) is zero
Then g isn't a recursive function either (but it is total of course).That's because the function g is different from every (total) recursive function on at least one value.

What is interesting here is that g is non-recursive regardless of how complex the function F itself is .

So if we define a real number such as:
0. g(0) g(1) g(2) g(3) g(4) ...
where the n-th digit is equal to g(n). This won't be a computable real number either.

(4) Regarding the topic of how it is of varying difficulty to show that a real number is computable just from description. Consider a function f:N→N such as:
f(x)=F(x,x)+1
F is the function from the third example. The function f is clearly total and non-recursive. Now consider the following real number:
0. all digits of f(0) + all digits of f(1) + all digits of f(2) + all digits of f(3) ...

In other words there is no marker as to when the values f(0), f(1), f(2) etc. end. What I mean here is that suppose we had f(0)=10, f(1)=6, f(2)=99, ... then the first few decimal places will be like:
0.10699...

Is the answer of computability of this real number independent of the function F? If it is, then is this real number always computable or always uncomputable?EDIT: Made some corrections and also added a question in the fourth example.

*** Actually 1-1 correspondence is of course not strictly necessary but this would be besides the point.

**** Well it isn't that obvious but F can be shown not to be a (total) computable/recursive function without too much difficulty.

 

[Jimster41]

In other words there is no marker as to when the values f(0), f(1), f(2) etc. end. What I mean here is that suppose we had f(0)=10, f(1)=6, f(2)=99, ... then the first few decimal places will be like:
0.10699...

Is the answer of computability of this real number independent of the function F? If it is, then is this real number always computable or always uncomputable?

All of that above is a lot to chew on and very interesting...

How wrong is it to cartoon it this way: A computable number is an example of a specific symbol that is repeatably accessible through some finite set of (repeatable?) symbolic steps. A non-computable number is one that cannot be specified (because specifying it would show it is computable).

w.t.h?

A related question (at least in my head) Is the set of algebra's (ways of specifying something) considered closed somehow or are there considered to be potentially infinitely many algebras?

 

[Greg Bernhardt]

Nice first Insight @trilobite!

 

[SSequence]

How wrong is it to cartoon it this way: A computable number is an example of a specific symbol that is repeatably accessible through some finite set of (repeatable?) symbolic steps. A non-computable number is one that cannot be specified (because specifying it would show it is computable).

w.t.h?

Well it would seem that it certainly depends how you define the words involved really. But, for example, many mathematicians (though not all) would agree that the definitions of reals (in post#8) described in examples (1), (2) and (3) are "well-specified", "well-defined", "well-described" (whatever you want to call it) but they will say that those real numbers do not have a computable decimal representation.

Perhaps when you used the word specified, you meant in the sense of being able to specify all the digits through a reasonably intuitive process? In that case the answer would depend on what one's opinion is regarding Church's Thesis.

For how to define precisely a computable real in decimal representation? That would be pretty easy.

First define any partial recursive/computable function f:N→N (where N={0,1,2,3,...}) as whatever a simple C-like program (to use a concrete example) of the following type could calculate:
int f (int x) {
// insert some program code
}
To define any partial recursive/computable function f:N x N→N whatever a simple C-like program of the following type could calculate:
int f (int x, int y) {
// insert some program code
}
and so on. Whenever the program is stuck in a loop and doesn't get to the "return" command, it is assumed that the function f isn't returning any value for that particular input (and hence the function f is considered partial in that case).

Obviously here it is assumed that the variables of type "int" are always greater than or equal to 0 (so negative values can't be taken as input or returned). As for what type of commands to include, you could really get away with absolutely minimal commands/control structures (but with more commands/structures its easier to write bigger and more understandable programs).

Having defined a partial computable function f:N→N, you can define a computable real, in decimal representation, as any total computable/recursive function (also taking care to consider the ambiguities related to 0.999...=1 --- so two different functions could represent the same real) of one variable for which:
0 ≤ f(n) ≤ 9 for all n > 0

Edit: I should perhaps mention that by itself, without any context, "computable real" might be a bit vague as a term. For example, suppose:
A = set of computable reals defined using decimal representation
B = set of computable reals (based upon some other idea)
In general, I don't think there would be any reason beforehand for the sets A and B to be equal (with A and B both being taken as proper sub-sets of R).

 

[trilobite]

Problems arise even from simple high school geometry. Here is my example. Keep in mind, this is not my main area of expertise.

I have been working on a physics-related AI project, and part of this project was developing an expert system. An expert system's two main modules are known as the knowledge base and the inference engine.

I decided to work on the inference engine first. I developed an automated theorem prover in LISP. This ATP uses first order predicate logic (FOPL).

After solving a few toy problems as a test, I turned my attention to Euclid's Element of Geometry. Since high school I regarded this as the quintessential book of infallible deductive logic. So I was shocked when I ran into difficulties in the very first proposition of Book 1. In this proposition, Euclid constructs an equilateral triangle in a very simple way. There seems no doubt that his proof is valid. Until, that is, one demands strict use of FOPL, with an acceptable set of axioms. By acceptable axioms I mean "self-evident truths" concerning what we now call Euclidean space.

Unfortunately, Euclid makes some steps in his first proof which are not justified, based on his initial set of axioms. It's very clear that what he is doing is mixing deductive logic, with statements based on looking at a diagram, and applying our common-sense notions concerning geometrical objects in 2D space. Yet I would say his proof is valid. I can perceive its truth. This tells me that at least for some cases, proof in the sense of strict formal logic is not required. So I say Euclid was doing the right thing by taking a practical approach. Now my belief in logic as the ultimate verifier of mathematical truth begins to fade a bit.

I knew beforehand that some of the earlier geometry theorem proving programs ran into difficulties, but I wanted to see for myself. I assumed that there must be some way of proving all of Euclid using FOPL, provided one had a sufficient set of axioms for each proof. Perhaps the old timers did not have powerful enough computers to handle this task? Perhaps their funding ran out? Or their expertise was demanded for more important problems?

My conclusion was not what some logicians would accept. I decided that Euclid was right, and that trying to fit every one of his proofs into the narrow confines of FOPL is perhaps not a useful approach. But I was still looking for the automated proof. Should I use a higher order logic? That raises other issues, such as the lack of any generally accepted automated proof method, comparable to proof by resolution for FOPL.

I looked into other techniques, such as found in the old PLANNER system. But PLANNER was never fully developed, in the sense of Hewitt's original proposal. I also tried PROLOG and ran into various problems. So I developed my own variation of backward chaining that works well. It runs in acceptable time using a LISP interpreter running on my PC. I decided to go ahead with FOPL because I saw no practical alternative.

Now the problem was the axioms I needed for each proof. I do not like my axioms. They are too complicated.

I looked in as many places as I could for someone who had actually published a complete automated proof, using FOPL, of Euclid, beginning with a relatively small number of simple axioms. Does it exist?

People talk about axioms sets of Hilbert, Tarski, and Birkhoff. But has anyone actually used one of these axiom sets and proved every one of the propositions of Euclid? Or have they come up with a published set of axioms and proofs of their own? A paper that only presents a small number of proofs does not impress me, because I can do the same thing quite easily. Also, I want a print-out from the program, not the human transcription.

I found out recently that in 2003 Meikle and Fleurot looked into Hilbert's geometry, as presented in his Grundlagen, and discovered some flaws. I'm not surprised. Even geniuses make mistakes. That is one reason we try to develop automated theorem provers and proof verifiers.

Far from giving up on this issue, it's something that still fascinates me. If nothing else, I have a FOPL theorem prover that works, and indeed without relying on recursion with backtracking. I won't say it's the fastest.

The other module is the knowledge base. When I look into how to represent math and physics knowledge, it's a more difficult problem than developing a FOPL prover. Of course it's often stated that we need second order logic. But as I said, I was beginning with what could be done using just FOPL.

On a more positive note, my favorite moment in this work was when my theorem prover made the constructions needed for Book I Proposition I. People might ask a human who solves this, "how did you come up with that idea?" Some would say it's human creativity or imagination. Or is it? In fact, it's just logic. Working only from the original axiom set, which of course excludes all the results of later proofs, what method do you have to prove that two lines are equal? The method my theorem prover came up with was that two lines are equal if they are both radii of the same circle. That is exactly what Euclid does.

But originally in the problem there is only a line, and no circles. I needed to add a construction axiom. Now the prover can constructs the circles. But it clearly has no "imagination" or "insight" or whatever other humanistic term you may use. It's just searching through many possibilities until it finds one that works.

My AI project has turned out to be much harder than I thought it would be. It's not like Chess programming, which I have studied. It was realized decades ago that creating a Chess program which could beat the world champion was only a matter of a faster processor and more memory. This could be seen by extrapolating a graph that showed the Chess rating vs. the hardware factors. I think this is because Chess is actually a simple problem, compared to geometry.

In conclusion, I think it's remarkable that for thousands of years humans taught Euclid's geometry as the best example of strict deductive reasoning. His reasoning method seems simple, so that even a young student can understand it. Euclid uses simple logic, and computers are logic machines. Yet creating a programmatic "Euclid in a box" turns out to be a challenging problem.

Thanks for describing your interesting (and ambitious!) project. [By the way, for some reason your post does not appear in "Discuss in the Community", at least not for me. Fortunately, I spotted it in Insights by scrolling down below my article, although usually I can't see any of the comments there, at all!]

 

[Aufbauwerk 2045]

Thanks for describing your interesting (and ambitious!) project. [By the way, for some reason your post does not appear in "Discuss in the Community", at least not for me. Fortunately, I spotted it in Insights by scrolling down below my article, although usually I can't see any of the comments there, at all!]

Thanks. Actually I thought perhaps I was posting in the wrong place, since it does not directly address your own post. (I'm new here). Perhaps it will be moved where people can see it more easily.

 

[Svein]

First define any partial recursive/computable function f:N→N (where N={0,1,2,3,...}) as whatever a simple C-like program (to use a concrete example) of the following type could calculate:
int f (int x) {
// insert some program code
}
To define any partial recursive/computable function f:N x N→N whatever a simple C-like program of the following type could calculate:
int f (int x, int y) {
// insert some program code
}
and so on. Whenever the program is stuck in a loop and doesn't get to the "return" command, it is assumed that the function f isn't returning any value for that particular input (and hence the function f is considered partial in that case).

Again, visit "Gödel, Escher, Bach" by Douglas Hofstadter. He discusses these concepts at length.

 

[SSequence]

Well I am aware of it and I have sort of flipped through it (reading a few paragraphs/pages here and there).

It seems to go into fair detail about what creativity could mean from a psychological perspective (a terms which I am using in a very broad sense including several categories -- but would go off topic to get into detail). I certainly like reading about that sort of stuff but certainly that isn't my main interest. My main interest is the mechanical perspective.

It just so happens that psychological perspective (using the word "psychological" in a slightly loose sense) also
is the one that relates directly to variety of practical applications while the mechanical perspective comes closer to maths (seemingly without much application). Anyway this is perhaps somewhat off topic.

--------

One point that is somewhat obvious (but could be mentioned) is that wikipedia mentions that all "algebraic numbers are computable". I am assuming (someone correct this if the interpretation is wrong) that this can be interpreted as "all real algebraic numbers have a computable decimal representation". Taking that previous point to be true, the original post mentions that it isn't known that pi.e or pi+e are transcendental or irrational. Now if someone showed that the decimal representation of these numbers isn't computable then it would follow that answer to former questions is yes.

 

[Svein]

Well I am aware of it and I have sort of flipped through it (reading a few paragraphs/pages here and there).

I do not think that is enough. Have you seen the chapter where he introduces the "programming languages" FLooP, BLooP and GLooP?

 

[SSequence]

No I haven't. Will read through those chapters some time.

 

[Aufbauwerk 2045]

I enjoyed this article very much. I would like to give it 5 stars. But when I try to do so, I am asked to "login in" even though I am already logged in. Do I lack the necessary membership level?

You are so right when you mention how our school math class glosses over certain things. Your example of the ellipse is very good. It seemed so simple when I learned the formula. It's even easy to construct an ellipse, using two pins and a string. I can measure the circumference by straightening out the string and using a ruler. So why is the math difficult?

As I understand math history, the whole point of the ratio is that we can divide any length exactly into a given number of unit lengths. That is what we mean by measurement. We should be able to find a unit length which can be used to divide both the diameter and the circumference.

My solution is to follow the rules and come up with the "correct" answer. I will use infinite series, irrational numbers, and so on, because the textbooks tell me that's the right way.

But in the back of my mind is the digital physics of Zuse, in which the most correct math is discrete, because our universe is a process carried out on some kind of cosmic grid. But as Zuse pointed out that raises its own problems, including a clash with relativity theory.

 

[Aufbauwerk 2045]

You are so right when you mention how our school math class glosses over certain things. Your example of the ellipse is very good. It seemed so simple when I learned the formula. It's even easy to construct an ellipse, using two pins and a string. I can measure the circumference by straightening out the string and using a ruler. So why is the math difficult?

Sorry, I left out an importance sentence, which I was thinking but failed to write down, so my reply makes no sense. This should read:

It's even easy to construct an ellipse, using two pins and a string. Then I can take another string and make it follow the curve of the ellipse. I can measure the circumference by straightening out the string and using a ruler. So why is the math difficult?

 

[trilobite]

I enjoyed this article very much. I would like to give it 5 stars. But when I try to do so, I am asked to "login in" even though I am already logged in. Do I lack the necessary membership level?

That used to happen to me, too (not that long ago.) For some reason, the feature works for me now. I don't think it has to do with membership level, but I have no idea why this happens.

 

[trilobite]

It's even easy to construct an ellipse, using two pins and a string. Then I can take another string and make it follow the curve of the ellipse. I can measure the circumference by straightening out the string and using a ruler. So why is the math difficult?

That's an excellent question, but I don't have an answer. It's one thing to live in a physical universe that is hard to understand, but as my article points out, "mysteries" lurk even in the ideal world of rudimentary geometry (squares, circles, ellipses!) It would be "nice" if the square root of 2 and pi were good old rational numbers. (Nice, but maybe boring!)

 

[trilobite]

But in the back of my mind is the digital physics of Zuse, in which the most correct math is discrete, because our universe is a process carried out on some kind of cosmic grid. But as Zuse pointed out that raises its own problems, including a clash with relativity theory.

Thanks for this interesting remark. My personal bias, for which I have no evidence, is that the "correct" math is continuous, although we use it to model a universe that is likely discrete.

 

[Svein]

Thanks for this interesting remark. My personal bias, for which I have no evidence, is that the "correct" math is continuous, although we use it to model a universe that is likely discrete.

Big fleas have little fleas,
Upon their backs to bite 'em,
And little fleas have lesser fleas,
and so, ad infinitum.

 

[Aufbauwerk 2045]

Big fleas have little fleas,
Upon their backs to bite 'em,
And little fleas have lesser fleas,
and so, ad infinitum.

Since humor is allowed, here is one of Bertrand Russell's favorites from his childhood.

What is mind? No matter.
What is matter? Never mind.

 

[Buffu]

Thanks for this interesting remark. My personal bias, for which I have no evidence, is that the "correct" math is continuous, although we use it to model a universe that is likely discrete.

Is there a proof that intergral of perimeter of an ellipse is can't not be written in terms of elementary functions or is it that nobody has found the solutions and it is a open problem ?

 

[trilobite]

Is there a proof that the perimeter of an ellipse cannot be written in terms of elementary functions or is it that nobody has found the solution and it is an open problem?

Great question! Unfortunately, I don't know the answer. Every reference I can find simply asserts that there is no elementary formula without giving any justification. If someone can comment with insight into this question, I would definitely be interested to hear it.

 

[Daniel Nason]

Algebra's for Algebras? Mathematics and spelling. Forty five years ago I could have enjoyed this. Uncomputable real numbers sound like a number with for example, digits that are wilfully generated as the number is created thru a truncating function such that each new digit is never predictable and a pattern never quite repeats. Of course each attempt at that number would yield a different result defeating the purpose of a number in the first place; such a number would be more a creation of science fiction (say a bistromatic drive for a spacecraft in a Douglas Adams universe). But uncomputable numbers? I'll read more and go to the sidelines and let others do the math. I have not tackled calculus in over forty years and I once took such pleasure in it!