Mathematics desk
< September 6	<< Aug \| September \| Oct >>	September 8 >

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

September 7

Chatin, turing machines and origin in coordinate systems.

In this article [1] Greg Chaitin makes a comparison between the choice of a Universal Turing Machine and the choice of origin in a coordinate system. Here is the relevant quote:

Algorithmic information theory focuses on individual objects rather than on the ensembles and probability distributions considered in Claude Shannon and Norbert Wiener's information theory. How many bits does it take to describe how to compute an individual object? In other words, what is the size in bits of the smallest program for calculating it? It is easy to see that since general-purpose computers (universal Turing machines) can simulate each other, the choice of computer as yardstick is not very important and really only corresponds to the choice of origin in a coordinate system.

Can anyone shed any more light on this interesting aside? Perhaps computation can be understood as traversal of some sort of convolution space in information? (no university education in mathematics, so please don't parse terms in technical senses).
Thanks, 86.132.15.29 02:07, 7 September 2007 (UTC)[reply]

Let M be some Turing machine, and let U be a universal Turing machine. Then there is a program P for U that will make it simulate M. In other words, giving input J to M is the same as giving input P+J to U, in which P+J consists of concatenating P and J on the input tape. If J is the shortest encoding of some object, then the Kolmogorov complexity of that object, using M as the machine, is |J|; call this number n. Using U as the machine, we find an upper bound |P+J| = |P| + n on the complexity. So using U as the measuring stick, we add at most a fixed number, |P|, to the complexity. Now if M is also a universal machine, it simulates U with some program |Q|, and so, by the same argument, using M as the measure of all things instead of U adds at most |Q| to their complexity. Putting m := max(|P|, |Q|), we see that the two measures using M and U never differ by more than the fixed value m. --Lambiam 05:35, 7 September 2007 (UTC)[reply]

I don't think he's trying to make a formal analogy between computability and geometry. I think he's simply saying that just as the choice of coordinate system is unimportant in geometry, so the choice of Turing machine is unimportant in algorithmic information theory. (edit: I do understand the reference. What I said still stands.) -- BenRG 10:49, 7 September 2007 (UTC)[reply]

This illustrates something I worry about when I write: An analogy is only helpful if readers understand the reference!

Take a blank sheet of paper as a representative of a Euclidean plane. If we want to lay out a Cartesian grid for coordinates, we must first choose some point as the origin. Maybe we choose the bottom left corner; maybe we choose the center of the page. Whichever point we decide to use, we can later change our mind and adjust the coordinates accordingly. Almost nothing we do is sensitive to the choice of origin.

Take a collection of universal Turing machines. Each one can simulate any Turing machine (since that's what "universal" means). In particular, each can simulate every one of the other universal machines. We can choose any machine we like as our "base" machine for measuring complexity. If we later change our mind, we can adjust. Almost nothing we do is sensitive to the choice of base. --KSmrq^T 14:51, 7 September 2007 (UTC)[reply]

You could even take it a step beyond that, and consider the thing being measured as completely independent of the coordinate system, as a rectangle is the same rectangle no matter where you put the origin and axes - you're just measuring it with different rulers, not measuring something different. In the same way, the thing being considered in terms of complexity is independent of what machine you implement it on - it's the same algorithm, being perfomed equivalently on different hardware, like a program running the same on any PC. It's not even relevant which one it's on, as long as it's being run correctly. On the subject of well-chosen analogies: this was apparently published in the International Journal of Theoretical Physics. It's likely that its intended audience was comfortable with symmetries of coordinate systems. In fact, I think that would count in this case as translating the concept into lay terminology. Black Carrot 18:02, 7 September 2007 (UTC)[reply]

Curiously this was the classical approach to geometry. The whole notion of a coordinate system is quite a modern notion. I know the Cartesian coordinate system was only introduced in 1637 by René Descartes. Does anyone know more of the history of the idea? --Salix alba (talk) 22:16, 8 September 2007 (UTC)[reply]

Well, here's my thoughts on that and perhaps some explaination of why i think the analogy might of consequence. The choice of origin makes no difference to the results of measure in some space but it does make a difference to the process of measure. In particular, if one is to measure the length of an object from a particular Point of Origin, then the difficulty will vary as a function three points: the origin, and two endpoints of the length in question. For example, the optimal origin to measure the distance between two points is their centre. Starting further away requires greater precision, thus more calculation. Incidentally, this also makes incompleteness intuitive as a result any origin being unable to measure the length of two points whose extension passes through it. (Remember that such distance or complexity is only defined for self-delimiting programs, i.e. those which do not halt. You can't distinguish finite and infinite distances along a line you can't measure.) 62.56.116.66 02:34, 9 September 2007 (UTC) (question poser)[reply]

What we're doing in "measuring" algorithmic complexity is counting the number of bits in a string. Since the strings involved, when using different "origins" (universal TM's), are about equally long (see above), and we use mathematical reasoning that ignores constant differences anyway, rather than actual counting, the choice can hardly be of influence on the "difficulty". The whole point of Chaitin's remark is in fact that the choice of universal TM is a non-issue. --Lambiam 03:39, 9 September 2007 (UTC)[reply]

Graphing Calculators

Which of the following graphing calculators is best in terms of its funcionality, price, reliability, etc...:

TI-83
TI-83+
TI-84

Thanks. Acceptable 20:59, 7 September 2007 (UTC)[reply]

The TI-83+ is basically a faster version of the TI-83 and has more memory; unless you have a lot of applications and games, it's not worth the extra money. The TI-84 also improves in the same way; it's faster and has more memory. Personally, I'd just go with the TI-83 and save yourself the money. Dlong 21:04, 7 September 2007 (UTC)[reply]

I created a page [2] to address this issue when I was teaching math. For most of my students I recommended a basic scientific calculator and not wasting their money on an 83/84/89. Donald Hosek 00:49, 9 September 2007 (UTC)[reply]

Thanks. As well, what additional functions does the TI-89 have that bans it from some nationalized math tests? Acceptable 21:06, 7 September 2007 (UTC)[reply]

The TI-89 basically extends the functionality of the TI-83 and -84 to include variables. For instance, the 83 and 84 for can find the value of a derivative at a specific point. For instance, if you ask for the derivative of

x^{1/2}

at x=3, the 83 and 84 gives you the numerical approximation, .28867514; The TI-89 gives you the exact value,

{\frac {\sqrt {3}}{6}}

; additionally, it will give you the derivative in terms of x,

{\frac {1}{2{\sqrt {x}}}}

. The TI-89 improves over the TI-83 and 84 in this way with regard to solving equations, using trigonometric functions, finding limits, and finding integrals, and many other things. Additionally, the TI-89 provides many other features, such as calculating Taylor series, finding the arclength of an equation, finding improper integrals, solving differential equations, and solving algebraic equations for complex solutions as well as real. Dlong 21:39, 7 September 2007 (UTC)[reply]

Last I checked, on tests (like the SAT) the TI-89 isn't banned... but the Voyage 200 and the TI-92 are, because of their qwerty keyboards. As for calculators, I don't think they make TI-83's anymore, as the 84 line has superseded it, and the best TI-84 is the TI-84 plus silver, but if you're looking for cheaper and won't be making/adding lots of programs it the TI-84 is probably what you want.

Speaking from experience, the TI-89 titanium/Voyage 200 (same OS, different shape) is one of the best calculators out there... but if you don't need all of its functionality, go with the TI-84 series. Gscshoyru 22:08, 7 September 2007 (UTC)[reply]

The reason that the TI-89 is often banned, as far as I know, is that it can easily [more easily?] store large amounts of text. Students can save a list of useful formulas, for example, then access it during the test, giving them an unfair advantage. This was a big problem in my chemistry class in high school (though this was before TI-89s) -- some of the kids had found the entire periodic table somewhere online and downloaded it onto their calculators as a program. (It would fail it you tried to execute, but all you had to do was look through the "code".) Tesseran

Good times. Why would that be a problem for the TI-83, though? I thought it could hold that. There's only, what, 200 elements? And each packet of information would be just a few characters long. Black Carrot 23:44, 7 September 2007 (UTC)[reply]

Even a regular TI-83 could hold way more text than you need -- I think it's just the ones with qwerty keyboards that are banned from stuff like the SAT, so you can't type the questions into it fast enough to store them all. (This is fallacious, as it would be simple to train yourself to do so, but, whatever.) Gscshoyru 00:00, 8 September 2007 (UTC)[reply]

You don't even need to do that. There's a TI83+ asm program that lets you turn your calculator on the side and type as if the calculator keys are a qwerty keyboard. Bit cramped but you can get used to it. Not that it's very useful for anything. Always amuses me when I read "No QWERTY keyboards!" when obviously any array of buttons large enough can be turned into one. BungaDunga 06:55, 11 September 2007 (UTC)[reply]

Can the regular TI-84 solve algebraic equations? For example, if I entered "3x^2+2x+3=0" (don't know if this quadratic eqn actually works) would it spit out the answer "x=...." ?Acceptable 02:42, 8 September 2007 (UTC)[reply]

Well... no calculator will know what you want if you do that, you have to explicitly tell them to solve. Under normal circumstances, I don't think TI-84's can solve quadratic equations and return all the solutions... but they may come with an add-on that does. Plus they have a solver, that will give you one of the answers. But if you want all the answers, TI-89 titanium is the way to go. Gscshoyru 02:50, 8 September 2007 (UTC)[reply]

Is the TI-84 PLus Silver Edition worth the extra $40? Acceptable 03:09, 8 September 2007 (UTC)[reply]

The 84 Silver is basically identical to the original except with even more memory (and possibly speed?). Unless you want to run an epic roleplaying game, or read Paradise Lost on a 96x64 screen or something, you don't need it. You can do just fine in school with an 83+ non-silver off EBay. 83+s only fit four or so applications (distinct from "programs" like games). I'm running a 3D/derivative Grapher, Omnicalc (a general functionality booster), Symbolic (extra math functions- arclength and derivatives mainly) and PrettyPrint, which displays expressions a lot like latex (equations you see on Wikipedia and how you'd write them). I could probably squeeze in a Tetris clone and maybe Asteroids. Note that an 83+ doesn't include a computer transfer cable (or a usb interface, so transfers are slooooww). Obviously if price isn't a huge issue an 84+ is better; from the ones I've tried the graphing speed (which is where you notice clock speed most, really) is far and away faster. Plus they have a USB port, which is theoretically hackable to interface with a USB memory stick and pull files off.BungaDunga 06:55, 11 September 2007 (UTC)[reply]

How many googols in a googolplex?

for the magic: the gathering players: i use a dryad arbor enchanted with utopia sprawl (creating blue mana) and freed from the real to create infinite green mana. i use this mana to play wurmcalling with buyback, putting exactly one googol green mana into x. this creates a 10¹⁰⁰/10¹⁰⁰ wurm token. considering i still have infinite mana at my disposal, i do this so that the sum of the tokens' respective powers is equal to a googolplex of damage. how many wurm tokens do i have to put into play to get this?

for the non-magic players: 10¹⁰⁰x = 10^{10^100}. see headline. DJRaveN4x 22:40, 7 September 2007 (UTC)[reply]

I don't think that in the old days it was possible to obtain unbounded mana. All those new cards with their fancy effects really messed up the game.

Anyway, applying the rule

{\frac {a^{b}}{a^{c}}}=a^{b-c}

gives:

x={\frac {10^{10^{100}}}{10^{100}}}=10^{10^{100}-100}=10^{9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999900}

.

But the shortest way to describe this number is simply "googolplex over googol". -- Meni Rosenfeld (talk) 23:06, 7 September 2007 (UTC)[reply]

i was really hoping the number was something a bit more tangible than that...but thanks a lot for the help! DJRaveN4x 23:18, 7 September 2007 (UTC)[reply]

Meni... I'm pretty sure there have been infinite mana combos in existence for a long, long time. Not sure when the first one came about. Or, if you're talking about the fact that you can't have "an infinite" amount of mana in your mana pool, you can't -- if you can do an action repeatedly, choose a number and do it that many times. And yes, I am magic rules freak. Oh well. Gscshoyru 23:58, 7 September 2007 (UTC)[reply]

The fact that you can only have unbounded, not infinite, mana, is something I have considered (and reflected in my phrasing) but not what I complained about. The time I was playing a lot was over 10 years ago - are you sure such tricks existed then? -- Meni Rosenfeld (talk) 07:11, 8 September 2007 (UTC)[reply]

It's all a consequence of the fact that 10ⁿ-n is still pretty darn close to 10ⁿ. So

10-1=9

10²-2=98

10³-3=997

10⁴-4=9996 etc.

So dividing a googolplex by a googol hardly makes a dent in it ! Of course, if you are looking for seriously large numbers, a googolplex is a tiddler compared to, say, Graham's number. Gandalf61 13:30, 8 September 2007 (UTC)[reply]

It takes away 99.99999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999% Isn't that some dent? --Lambiam 03:44, 9 September 2007 (UTC)[reply]

Well, yes, to be precise I should have said dividing a googolplex by a googol appears to hardly make a dent in it. This is because the ratio of the logs of a googolplex and googolplex/googol is very close to 1. 1000000000000000000 is only 1% of 100000000000000000000, but they appear to have a similar magnitude. Gandalf61 09:07, 9 September 2007 (UTC)[reply]

Completely irrelevant to the mathematics, but I know I worked out an infinite mana combo that was valid around 4th edition. Given how broken some of the earlier cards were before they got errata'd or restricted, I wouldn't be surprised if it was possible in Alpha or Beta. Confusing Manifestation 01:19, 12 September 2007 (UTC)[reply]

Syntax of multiple derivatives

When you take the 2nd derivative of something, say x(t), it is written d²x/dt². Why is it not written dx²/dt² or d²x/d²t? Why are the superscipts not in the same place in the numerator and denominator? jwillbur 22:58, 7 September 2007 (UTC)[reply]

The short answer is that the squares don't have the same meaning in the numerator and denominator. Informally speaking, in the numerator your square the differential operator (in other words, you take x and apply the operator d to it twice) and in the denominator you square the differential itself (you apply d to t, and multiply the result by itself).

Another informal way to motivate this notation is that

x''(t)={\frac {d\left({\frac {dx}{dt}}\right)}{dt}}={\frac {d(dx)}{dt\cdot dt}}={\frac {(dd)x}{dt^{2}}}={\frac {d^{2}x}{dt^{2}}}

.

-- Meni Rosenfeld (talk) 23:13, 7 September 2007 (UTC)[reply]

Also, for any well-behaved x,

{\frac {dx}{dt}}{\frac {dt}{dx}}=1

, but in general

{\frac {d^{2}x}{dt^{2}}}{\frac {d^{2}t}{dx^{2}}}\neq 1

. The notation is consistent with this. (For single derivatives they "cancel" but not for higher orders.) —Keenan Pepper 05:53, 8 September 2007 (UTC)[reply]

Another way of looking at it is viewing d/dt (differentiation with respect to t) as an operator, and the meaning of the expression d²x/dt² is then

{\frac {d}{dt}}\left({\frac {d}{dt}}\,x\right).

Using the convention that f²(x) is short for f(f(x)), we can rewrite this to:

\left({\frac {d}{dt}}\right)^{2}x\,\!,

from which it is a small step to

{\frac {d^{2}}{dt^{2}}}\,x={\frac {d^{2}x}{dt^{2}}}.

If I were to encounter dx²/dt² in mathematical writing, my first assumption would be that this means the same as (dx/dt)², which is something entirely different. --Lambiam 04:04, 9 September 2007 (UTC)[reply]