Search All of the Math Forum:

Views expressed in these public forums are not endorsed by NCTM or The Math Forum.

Notice: We are no longer accepting new posts, but the forums will continue to be readable.

Topic: Re: "Somewhat rational" numbers
Replies: 8   Last Post: Oct 29, 2017 6:51 AM

 Messages: [ Previous | Next ]
 magidin@math.berkeley.edu Posts: 11,749 Registered: 12/4/04
Re: "Somewhat rational" numbers
Posted: Oct 28, 2017 4:46 PM

On Friday, October 27, 2017 at 11:51:34 PM UTC-5, josh...@gmail.com wrote:
> > All of your numbers are examples of "computable numbers": there is an algorithm to write down their digits. For some of them, the algorithm is difficult, and may require a lot of "memory" (such as pi, though there are now algorithms that allow you to compute any specific digit of pi without having to compute all previous ones). Some require less (such as your y and z). They have simple algorithms.
>
> Thanks for a new perspective. I wonder whether we can think of a number which isn't "backed up by an algorithm". Do such rogue numbers (on the line of rogue stars and planets) exist?

Please stop inventing names that are your own personal nomenclature; better to ask if a name already exists. Otherwise, you end up making statements that are nonsensical on their face, like your talk about "somewhat rational numbers". That's just as nonsensical as "a little bit pregnant".

"Backed up" has a meaning in computer science. It has NOTHING to do with what you are talking about here. Introducing the technical term that has a meaning to mean something else makes what you write confusing at best, and outright silly or wrong at worst.

Are there numbers that cannot be computed by an algorithm? The first issue on that question is just what is and what is not an algorithm.

Most people accept Church's Thesis: that the concept of "Turing machine" (or any of the many concepts that are mathematically equivalent to it) actually does in fact capture the intuitive notion of what an algorithm is. So that something is an algorithm if and only if it can be performed by a Turing machine. If that is the case, then the number of algorithms is countable, because the number of distinct Turing machines is countable. And since there are uncountably many numbers, it follows that "most" real numbers cannot be computed by an algorithm.

Church's thesis cannot be "proven", because it connects an intuitive notion for which we have no formal definition ("algorithm") with a formal one ("Turing machine"). It could be *disproven*, if someone where to produce something that everyone agrees should by rights be called an algorithm but which we can prove cannot be performed by a Turing machine. Nobody has managed to do that, however. But if such a thing were possible, it still seems like the number of possible algorithms is at most countable, since they would require some sort of description, and there are only countably many possible descriptions. So even in that situation, it is reasonable to conclude that there are many numbers that cannot be computed; that is, the set of computable numbers is countable, even if you expand the notion of "algorithm".

--
Arturo Magidin

Date Subject Author
10/27/17 Guest
10/27/17 Peter Percival
10/28/17 joshipura@gmail.com
10/28/17 Peter Percival
10/28/17 magidin@math.berkeley.edu
10/28/17 bursejan@gmail.com
10/28/17 bursejan@gmail.com
10/29/17 Peter Percival
10/29/17 FromTheRafters