Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Insights Simple Geometry, Deep Math - Comments

  1. Jan 21, 2017 #1
  2. jcsd
  3. Jan 22, 2017 #2
    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.
  4. Jan 22, 2017 #3
    Yes, that's a fascinating topic! Thanks for mentioning it.
  5. Jan 27, 2017 #4
    care to explain a bit what the def of a non-computable number is?
  6. Jan 27, 2017 #5
    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?
  7. Jan 31, 2017 #6
    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?
  8. Jan 31, 2017 #7
    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 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.
  9. Jan 31, 2017 #8
    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:

    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

    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 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:

    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.
    Last edited: Jan 31, 2017
  10. Feb 2, 2017 #9
    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).


    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?
  11. Feb 2, 2017 #10
  12. Feb 2, 2017 #11
    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 wanna 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).
    Last edited: Feb 2, 2017
  13. Feb 5, 2017 #12
    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!]
  14. Feb 5, 2017 #13
    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.
  15. Feb 6, 2017 #14


    User Avatar
    Science Advisor

    Again, visit "Gödel, Escher, Bach" by Douglas Hofstadter. He discusses these concepts at length.
  16. Feb 6, 2017 #15
    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.
  17. Feb 6, 2017 #16


    User Avatar
    Science Advisor

    I do not think that is enough. Have you seen the chapter where he introduces the "programming languages" FLooP, BLooP and GLooP?
  18. Feb 6, 2017 #17
    No I haven't. Will read through those chapters some time.
  19. Feb 8, 2017 #18
    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.
  20. Feb 12, 2017 #19
    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?
  21. Feb 13, 2017 #20
    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.
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted

Similar Discussions: Simple Geometry, Deep Math - Comments
  1. Simple Geometry (Replies: 2)

  2. Simple math (Replies: 5)

  3. Simple math (Replies: 5)