Wikipedia:Reference desk/Archives/Mathematics/2010 July 10

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.

July 10

Online virtual Turing machine

I'm working on Turing machine programs, but after a while it gets tedious to go through all of the steps manually. Is there someplace online which will allow me to enter a Turing machine program and the input value, and will then simulate the Turing machine? --138.110.206.101 (talk) 21:24, 10 July 2010 (UTC)

Googling "Turing machine simulator" throws up a few candidates. Gandalf61 (talk) 17:33, 11 July 2010 (UTC)

Cosets

Hi. I am currently battling my way through a book on Group Theory and am having a bit of trouble with cosets. We have already stated that for a group G with a subgroup H and an index set I with the element $t_{i}$ being an element of the ith coset, $G=\bigcup _{i\in I}Ht_{i}$. We are now attempting to prove that $G=\bigcup _{i\in I}{t_{i}}^{-1}H$ is a decomposition of G into distinct left cosets. The first observation made is that if ${t_{i}}^{-1}H={t_{k}}^{-1}H$ then we must have ${t_{k}}{t_{i}}^{-1}\in H$ and hence $H{t_{k}}=H{t_{i}}$, which is impossible unless i=k. How exactly have we established $H{t_{k}}=H{t_{i}}$? Is it simply by saying that because we know ${t_{k}}{t_{i}}^{-1}\in H$, then $H{t_{i}}$ and $H{t_{k}}$ must be in H also and so we can form the respective left cosets and set them equal to each other? Or have we performed some inversion such as $(tH)^{-1}=Ht^{-1}$, where H is its own inverse, of sorts? That suggestion may be complete and utter rubbish; just remember, I'm new to this. Then it says i=k; is this just using that two cosets are either identical or have no element in common? I have more questions but I don't want to make this too long and scare off and potential readers so I'll save them until I have a response! Thanks asyndeton talk 21:53, 10 July 2010 (UTC)

You are right (informally) that you invert both sides of ${t_{i}}^{-1}H={t_{k}}^{-1}H$ to get $Ht_{i}=Ht_{k}$. To prove this, take $g\in Ht_{i}$, then $g=ht_{i}$ for $h\in H$. Then $g^{-1}=t_{i}^{-1}h^{-1}\in t_{i}^{-1}H=t_{k}^{-1}H$, so $g^{-1}\in t_{k}^{-1}H$... see where this is going? Finish that argument (to show $g\in Ht_{k}$), and you'll have shown $Ht_{i}\subseteq Ht_{k}$. The converse inclusion is exactly the same, with i and k swapped. Staecker (talk) 23:13, 10 July 2010 (UTC)

Thanks Staecker, I found that very helpful! It was also quite illuminating for the other questions I was planning to ask, so I shan't need to post them. Thanks again! asyndeton talk 13:11, 11 July 2010 (UTC)

1+1=1

I was surprisingly asked this question in an Arabic forum:

When can 1+1=2? I mean 1+1=1?

I answered: Impossible mathematically, but might be possible if it were a philosophical puzzle.

I knew then the one asked me had a Ph. degree in Maths and said it was possible in Mathematics and as an exceptional case related to Relativity theory. Does this make sense? Help me please! --Email4mobile (talk) 22:08, 10 July 2010 (UTC)

You probably mean: when can't 1+1=2 ? i.e. when can 1+1≠2, right?

Since you're looking for an answer in Relativity theory, so I think it's really rather simple and trivial (for anybody who has learnt that scientific discipline): let's assume that - when travelling at a speed of 1 mile per minute - you meet another vehicle travelling to the opposite direction at a speed of 1 mile per minute; then you won't see it travel at a speed of 2 miles per minute, although this is what should be expected intuitively.

The reasoning behind this phenonemon is that the mathematical operation required here is not a simple "addition" (+), so it's not really 1+1≠2...

HOOTmag (talk) 22:30, 10 July 2010 (UTC)

I think that if ZFC is inconsistent and you base your definitions of integers on sets, then "1+1≠2" is provable.

Other than that - if by 1, 2 and + you mean the integers and integer operation, then no, 1+1 can't be unequal to 2. But mathematical notation is overloaded, and you can use those symbols to mean different things. One way is to use + to mean some form of relativistic addition as explained by HOOTmag. This is usually defined for numbers less than 1, corresponding to fractions of the speed of light, as

$u\oplus v={\frac {u+v}{1+uv}}$

You can also have a probabilistic addition, corresponding to disjunction of independent events:

$u\oplus v=u+v-uv$

For general positive numbers you also have Pythagorean addition:

$u\oplus v={\sqrt {u^{2}+v^{2}}}$

All of these operations might be denoted by "+" itself if the context makes it more convenient.

Also, 1+1 can be -1, 0, 1, 10 or 11 depending on whether you use a field of characteristic 3, 2, boolean algebra, binary base or gray code. -- Meni Rosenfeld (talk) 05:14, 11 July 2010 (UTC)

I really am sorry for not revising what I wrote (probably because of that PhD). I meant 1+1=1? Can I/someone correct the title?

You can change the title when you edit the section - it's at the top of the edit window. I've done it for you.

So yes, 1+1=1 in relativistic and probabilistic addition, and in boolean algebra. Also in the real numbers modulo 1. -- Meni Rosenfeld (talk) 05:16, 11 July 2010 (UTC)

The far I know is that in Boolean operations + in this context refers to OR, not really addition. Addition in binary logic is still the same as any mathematical basic operation (i.e. 1 + 1 = 10 in binary system).

Regarding relativistic and probabilistic addition, I'm not well aware but I suppose there should be similar explanation or Mathematics would be explained in many wrong ways.--Email4mobile (talk) 05:42, 11 July 2010 (UTC)

Read my post again. "Addition" and "+" can refer to many things. When they refer to integer addition then yes, 1+1=2 and 1+1≠1. When they refer to something else the result can be different. You need to know what the "+" means whenever you encounter it (in the vast majority of cases it will be integer\real addition). And yes, it's the same addition in the binary\gray examples, just a different notation for the numbers. -- Meni Rosenfeld (talk) 06:33, 11 July 2010 (UTC)

Thanks Meni Rosenfeld. I was just afraid if there were really some exceptions in mathematics regarding basic operations. When it comes into notations then I will assume the man who asked me was absolutely right, although he should not have paid much attention for tht.--Email4mobile (talk) 08:29, 11 July 2010 (UTC)

Anyways, the man who (according to your testimony) is looking for a "relativistic" answer, has undoubtedly meant that - when you travel at the speed of light and you meet another vehicle travelling to the opposite direction at the same speed, then you won't see it travel at twice the speed of light, but rather at the speed of light...HOOTmag (talk) 11:46, 11 July 2010 (UTC)

Did I miss it, or did no one mention the additive trivial group?—msh210℠ 15:26, 13 July 2010 (UTC)

As an additive group, it doesn't have a 1 but rather a 0. 0+0=0 is not very unusual. -- Meni Rosenfeld (talk) 17:58, 13 July 2010 (UTC)

D'oh! You're right, of course, by convention (though naturally what symbol is used for the element of a trivial group is arbitrary, and '1' (or '5', or '}', or anything) can be used as well as '0').—msh210℠ 18:20, 13 July 2010 (UTC)

Girls, buses, cats AGAIN.

Hi all,

On a late-night gambling game show, the old chestnut was posed:

Five girls are traveling by tourist bus. Each girl has 5 baskets, each basket has 5 cats, and each cat has 5 kittens. The bus stops and 3 girls get off. How many legs are on the bus?

I figured, great, I'll use some of my free cellphone money that keeps piling up to send the R7.50 SMS to try my luck. It's obvious: Each basket has 5 cats +5*5 kittens = 30 cats = 120 legs, so each girl has 120*5 = 600 legs + 2 of her own = 602; 2 girls mean 1204 legs, duh.

Someone guesses that before they call me, and it's wrong. Oh, right, sneaky! The girls get off, leaving their cats behind, so 3004 legs left. Wash, rinse, repeat. Oh, right, the driver! 3006 then. Someone guesses that too. Also wrong. Same with 1206 (assuming a driver, but the girls take their livestock with them.)

The answer they finally gave was 2708. What? I can't figure out how that came to be. Any ideas? --Slashme (talk) 23:50, 10 July 2010 (UTC)

err... I hate to point it out, but there aren't any legs on the bus. Busses have wheels. --Ludwigs2 23:57, 10 July 2010 (UTC)

No idea. Well, a couple. Maybe there were 751 boys on the bus? Or, a shipment of prosthetic legs in the cargo hold? By the way, was this the 3:42 for St. Ives? I hate it when I have to take that bus.... --Trovatore (talk) 00:02, 11 July 2010 (UTC)

Trovatore alluded to the rhyme As I was going to St Ives. -- Wavelength (talk) 00:58, 11 July 2010 (UTC)

I'm pretty sure it's a scam. 74.15.137.192 (talk) 00:41, 11 July 2010 (UTC)

SlashMe, if this is that BrainBox game that comes on TV at night then it's an absolute scam and you've just wasted your airtime. A few months ago I read an article in the Cape Argus about how what they're doing is not technically illegal (they always award the prize if someone figures out the convoluted reasoning) but the puzzles themselves use so many unnamed assumptions that they are basically bogus and just a front to scam people of their money. Regards. Zunaid 06:56, 11 July 2010 (UTC)

OK, thanks everyone. I guess it was a school bus: I got schooled! --Slashme (talk) 08:08, 11 July 2010 (UTC)

There's a 'Running Car' from 'Origami to Astonish and Amuse' by Jeremy Shafer, at [1], it's the last model on the page. The car has four legs, but he's known for being truly demented and I don't think it would work full scale ;-) Dmcq (talk) 11:34, 11 July 2010 (UTC)