## Question

Math help on Congruences, Modulo, Fermat's Theorem, Fermat's Last Theorem (FLT), Euler's Theorem, Euler Totient Function, Divisors, Multiples, Prime Numbers, Prime Number Theorem, Distribution of Prime Numbers, Dzeta Function, Riemann Hypothesis, Algebraic Number Theory, Analytic Number Theory on My Math Forum.
Math problems in Number Theory

### Re: Question

PS - Thank you for putting up with my sloppy notation!!
krausebj0

Posts: 599
Joined: Thu Nov 24, 2011 2:12 am

### Re: Question

johnr wrote:
CRGreathouse wrote:
Hoempa wrote:Given any transcendental number between 0 and 1. Replace all 0s and 1s by 2s and 3s respectively. Could this number still be transcendental?

Indeed, it would automatically be transcendental; the proof is not hard.

Ok, you gave the answer that I suspected was true, but the question was way out of my league to answer. Can you share the proof, or at least a sketch?

I think this is an interesting problem. I don't see the easy proof if there is one.

There's a similar proposition that is easy to prove. If a number is irrational, then doing any number of digit replacements also results in an irrational number. That's true, because if there's a repeating pattern in the original numbers' decimal expansion; the modified decimal will also have a repeating pattern.

But transcendentals seem to be much harder. Say .a1a2a3a4... is a transcendental number. And say I replace all the 1's with 7's. Is that number transcendental? Why should it be? I've never heard of any connection between a number being transcendental, and any particular property of its decimal expansion.

Take e - 2 = .71828... (to keep it between 0 and 1). That's transcendental. Change all the 1's to 0's, so it's

.70828...

Is that transcendental? There doesn't seem to be any way to either prove this or come up with some clever counterexample. If this is an easy problem I don't see it.

Maschke
King of Diamonds

Posts: 375
Joined: Sun Aug 26, 2012 6:53 pm

### Re: Question

It probably depends on the transcendental and the replacement digit.

Liouville's Constant is transcendental but if you replace all 1's with 0's you get the integer 0

If instead you replace all 0's with 1's you get the rational 10/9

http://mathworld.wolfram.com/LiouvillesConstant.html

Click below for excellent math help tutorials!

I WANT TO BELIEVE THE TRUTH IS OUT THERE In a Dimension not only of SIGHT and SOUND ... but of MIND.

Who loves ya baby ? -KOJAK

agentredlum
Super User

Posts: 2734
Joined: Fri Jul 01, 2011 6:32 pm
Location: North America, 42nd parallel

### Re: Question

You can't simply redefine what a Turing machine is and claim you have a proof.
johnr
Super User

Posts: 1500
Joined: Sun Apr 15, 2012 7:55 am

### Re: Question

krausebj0 wrote:PS - Thank you for putting up with my sloppy notation!!

While I am pleased with your less belligerent tone and am inspired to drop some of my own sarcasm as a friendly gesture, the issue is no mere matter of sloppy notation. Sloppy notation is of course a significant issue when one is presenting something as a proof. Nothing can be a proof unless it is clear what it does and does not say and that is why there are standards of notational propriety in proof-theoretic fields like math and logic.

But when you say that you "proved" that your ostensible Turing machine produces infinite output per step, all that you can possibly have really proved is that your procedure can't be done on a real Turing machine. Personally, I suspect that this Turing talk is just a side issue best dropped. What you need is simply an orderly procedure that provably captures all that you need to capture. For reasons I've already mentioned involving the existence of infinitely many numbers between 0 and 1 whose binary representation will include both infinitely many 0s and infinitely many 1s with not pattern, hence obviously no computable pattern, to how the 0s and 1s are distributed with respect to each other, I repeat once again that what you THINK you can do truly cannot be done. I will add that I suspect that the reason you think it can be done is that you are actually looking only at a few cases of finitely many zeros strewn amongst an infinity of 1s (or vice versa) and prematurely adding a "..." that you ASSUME will take you where you need to go, but clearly won't.
johnr
Super User

Posts: 1500
Joined: Sun Apr 15, 2012 7:55 am

### Re: Question

Maschke wrote:

I think this is an interesting problem. I don't see the easy proof if there is one.

There's a similar proposition that is easy to prove. If a number is irrational, then doing any number of digit replacements also results in an irrational number. That's true, because if there's a repeating pattern in the original numbers' decimal expansion; the modified decimal will also have a repeating pattern.

But transcendentals seem to be much harder. Say .a1a2a3a4... is a transcendental number. And say I replace all the 1's with 7's. Is that number transcendental? Why should it be? I've never heard of any connection between a number being transcendental, and any particular property of its decimal expansion.

Take e - 2 = .71828... (to keep it between 0 and 1). That's transcendental. Change all the 1's to 0's, so it's

.70828...

Is that transcendental? There doesn't seem to be any way to either prove this or come up with some clever counterexample. If this is an easy problem I don't see it.

Let me back track the discussion a bit.

Any irrational between 0 and 1 would have infinitely many 0s and 1s. If it had only finitely many 1s, then it's infinite tail would be nothing but zeroes and it would therefore be a rational number and not even a rational number with repeating segments, but equivalent to a number of the form x/y where y is some finite power of 2. If, on the other hand, there were only finitely many 0s and a long tail consisting of 1s, then the number would behave like numbers with a long tail of nothing but 9s in the decimal system, and would therefore again be rational.

Next, there can't be ANY pattern to the distribution of the 1s and 0s with respect to each other. If there were a repeating pattern, then the number would once again be rational, But I invoked transcendentals precisely because I was discussing Turing machines, ie real Turing machines that plod along one operation at a time for a finite time. So I wanted to avoid discussion of any irrational for which there might be some clever program that a Turing machine might in any way be able to use to "find" and identify the irrational in question. I wanted fully uncomputable numbers. So I chose transcendentals as what I took to be the obvious, or at least AN obvious case to highlight.

Now, the reason I was, and am, inclined to believe what CRG said was precisely my intended meaning of "no pattern to the distribution whatsoever", which I'd be inclined to say would keep us in the realm of the non-computable regardless of what the two digits are. However, to even include both 2 and 3, we need to be at least in base 4 and I am not sure whether the mere fact that only 2 of the four available digits appear might not already be too much pattern to assume that the number is transcendental.

So what we really need is some rigorous defining of what it means to have no pattern whatsoever.
johnr
Super User

Posts: 1500
Joined: Sun Apr 15, 2012 7:55 am

### Re: Question

johnr wrote:
krausebj0 wrote:PS - Thank you for putting up with my sloppy notation!!

While I am pleased with your less belligerent tone and am inspired to drop some of my own sarcasm as a friendly gesture, the issue is no mere matter of sloppy notation. Sloppy notation is of course a significant issue when one is presenting something as a proof. Nothing can be a proof unless it is clear what it does and does not say and that is why there are standards of notational propriety in proof-theoretic fields like math and logic.

But when you say that you "proved" that your ostensible Turing machine produces infinite output per step, all that you can possibly have really proved is that your procedure can't be done on a real Turing machine. Personally, I suspect that this Turing talk is just a side issue best dropped. What you need is simply an orderly procedure that provably captures all that you need to capture. For reasons I've already mentioned involving the existence of infinitely many numbers between 0 and 1 whose binary representation will include both infinitely many 0s and infinitely many 1s with not pattern, hence obviously no computable pattern, to how the 0s and 1s are distributed with respect to each other, I repeat once again that what you THINK you can do truly cannot be done. I will add that I suspect that the reason you think it can be done is that you are actually looking only at a few cases of finitely many zeros strewn amongst an infinity of 1s (or vice versa) and prematurely adding a "..." that you ASSUME will take you where you need to go, but clearly won't.

The process completes when Ai' = D and Ai = I (it has been proven that Ai' = D iff Ai = I). The process follows the order of D, so Ai' will equal D. The output is all possible ind. Once the output is equal to all possible ind, then all possible i_n have been included in Ai. This is why Ai = I. If the turing machine can enumerate all possible ind, then the final step (ie... the computer halts), when the last ind has been enumerated (thus enumerating the last i_n). This is a turing machine. Instead of your unspecified definition, I will look to the inventor's:

Turing gave a succinct definition of the experiment in his 1948 essay, "Intelligent Machinery". Referring to his 1936 publication, Turing wrote that the Turing machine, here called a Logical Computing Machine, consisted of:

...an unlimited memory capacity obtained in the form of an infinite tape marked out into squares, on each of which a symbol could be printed. At any moment there is one symbol in the machine; it is called the scanned symbol. The machine can alter the scanned symbol and its behavior is in part determined by that symbol, but the symbols on the tape elsewhere do not affect the behavior of the machine. However, the tape can be moved back and forth through the machine, this being one of the elementary operations of the machine. Any symbol on the tape may therefore eventually have an innings.[2] (Turing 1948, p. 61)
krausebj0

Posts: 599
Joined: Thu Nov 24, 2011 2:12 am

### Re: Question

Are you telling me that you never tried to union together ALL elements of RI before? Unioning together all elements of P(N) is no fun... It equals N by the time you get through just the evens and the odds.

Just for fun, why don't you try unioning all reals together, where the reals are expressed as outputs of my turing machine?
krausebj0

Posts: 599
Joined: Thu Nov 24, 2011 2:12 am

### Re: Question

I'll give you the original hint one more time:

The output is the balance sheet. The tape is the income statement.

CPA's ROCK!!!!!!!!
krausebj0

Posts: 599
Joined: Thu Nov 24, 2011 2:12 am

### Re: Question

You can call me wrong John, but you best not mess with Turing.

I once thanked you for not accepting that which has not been proven true. Maybe I was wrong though...
krausebj0

Posts: 599
Joined: Thu Nov 24, 2011 2:12 am

### Re: Question

I split off two of your posts. The disproof of Cantor's theorem I moved here
viewtopic.php?f=27&t=25259

on the Set Theory forum, while the "greatest paradox" I moved here
viewtopic.php?f=38&t=25260

on the Other Topics forum.

Again, thank you all.
krausebj0

Posts: 599
Joined: Thu Nov 24, 2011 2:12 am

### Re: Question

krausebj0 wrote:You can call me wrong John, but you best not mess with Turing.

I once thanked you for not accepting that which has not been proven true. Maybe I was wrong though...

I'm not messing with Turing, you are.
johnr
Super User

Posts: 1500
Joined: Sun Apr 15, 2012 7:55 am

### Re: Question

krausebj0 wrote:I'll give you the original hint one more time:

The output is the balance sheet. The tape is the income statement.

CPA's ROCK!!!!!!!!

I know some CPAs who rock within their own zone of expertise. My weight lifting guru is a female accountant working towards her CPA. She is great with weights, diet advice, handling dogs (where I met her) and I'm sure at her job. She is also not prone to making vague accounting analogies and pretending they are rigorous proofs of anything. So she rocks in several ways.
johnr
Super User

Posts: 1500
Joined: Sun Apr 15, 2012 7:55 am

### Re: Question

krausebj0 wrote:Are you telling me that you never tried to union together ALL elements of RI before? Unioning together all elements of P(N) is no fun... It equals N by the time you get through just the evens and the odds.

Just for fun, why don't you try unioning all reals together, where the reals are expressed as outputs of my turing machine?

OK, let C denote a set of subsets of all the reals in a given interval such that every real in that interval is an element in at least one of these sets. Then the union of those subsets is of course the set of all reals in that interval. This is about as trivial as it gets in set theory. The problem is knowing that all the reals in the complete set of reals associated with the interval really is in one of these sets and I guarantee you that about the last thing you want to use to try to demonstrate this is a Turing machine. Turing machines ARE, on the other hand, good at generating FINITE strings of 0 and 1 of arbitrary lengths. But not only no transcendental numbers or irrational numbers in general, but no rational number that repeats in binary notation is finitely long. So it's not trivial to distinguish among even a rational that appears to repeat .01010101... for 472 squidillion places but then STOPS vs one that really does repeat forever vs one that seems to equal one or the other over the first 472 squidillion places and then "goes irrational". There may not be enough time in the rest of the life of the universe to determine which of these three numbers you really have in a given case.

I'm no expert on Turing machines nor do I aspire to be, but I'm familiar with them from my grad school days in linguistics and of course know more about them now that I spend a lot more time on pure math. So it pains me to see the real and serious questions of the limits of knowledge that these universal calculating machines can be used to asked mocked by discussions of Turing machines that produce infinite outputs in one step, etc.
johnr
Super User

Posts: 1500
Joined: Sun Apr 15, 2012 7:55 am

### Re: Question

Locked at author's request.
Pari/GP: this is the program I probably mentioned in my post. Windows users can get it at http://pari.math.u-bordeaux.fr/pub/pari ... -2-6-2.exe

CRGreathouse
Global Moderator

Posts: 12566
Joined: Sat Nov 25, 2006 9:52 am
Location: UTC -5

Previous