Mathematics desk
< August 9	<< Jul \| August \| Sep >>	August 11 >

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.

August 10

Question about Time and Complexity Class RE

Does there exist for every Turing Machine T a Turing Machine S that always halts and if T halts on input x, then S will take more steps than T to halt on x? Just curious. Thanks:-) 209.252.235.206 (talk) 08:26, 10 August 2011 (UTC)[reply]

No. Suppose T is such that the set of inputs on which it halts is not computable. Then if there were such an S, you could compute the halting set of T as follows: Given any input x, simulate S as applied to x until it halts, and count the number of steps that takes. Then simulate T as applied to x for that many steps. If it hasn't halted yet, it isn't going to. --Trovatore (talk) 09:08, 10 August 2011 (UTC)[reply]

That's what I was thinking, but wouldn't that require some way to get S from T or some other method of linking the two? 209.252.235.206 (talk) 09:20, 10 August 2011 (UTC)[reply]

Actually, it's late and I'm not thinking, you're right. I have another question: given T is there a machine S that always halts and if T halts at x, then S returns the same value as T at x? When I say value, etc., I am thinking in terms of computable maps. Sorry, it's been a while since I've worked with any of this:-) [Does every partial recursive function extend to a total recursive one?] 209.252.235.206 (talk) 09:23, 10 August 2011 (UTC)[reply]

No, via a very similar argument. If T is a machine, you can make a machine T' that halts precisely when T does, and on input x, T' outputs the number of steps it takes T to halt. Then if you could extend T' to a total recursive function S, you could decide if T halts on x by running T on x for S(x) steps.--Antendren (talk) 09:37, 10 August 2011 (UTC)[reply]

Thank you:-) I had a feeling this wasn't possible... 209.252.235.206 (talk) 09:40, 10 August 2011 (UTC)[reply]

Is zero really an even number?

I'm not quite convinced by the simple answer, given to me by a friend who teaches primary school mathematics, that it is even because it is the integer between -1 and 1, which are both easily proved to be odd numbers. Roger (talk) 11:08, 10 August 2011 (UTC)[reply]

If n is an integer, then 2n is an even number. The case n=0 shows that 0=2n is even. Bo Jacoby (talk) 11:21, 10 August 2011 (UTC).[reply]

We have an article parity of zero. Algebraist 11:43, 10 August 2011 (UTC)[reply]

The thing that always mystifies me about this question is, why does anyone have any doubts about it? I've read the various explanations but none of them resonates. Roger Dodger, could you please relate what it is that made you uneasy about accepting that zero is even? --Trovatore (talk) 19:54, 10 August 2011 (UTC)[reply]

I think it has to do with the fact that people have difficulty with the concept of 0 itself. I don't know what it is if they're comfortable with -2 being an even number. --COVIZAPIBETEFOKY (talk) 02:18, 11 August 2011 (UTC)[reply]

I have no problem with 0 being even as such, I just found my friend's explanation to be too simplistic and unconvincing. Perhaps it is acceptable to his 6th grade class but to me it seems not much better than an argument from authority. Thanks for the article link, it does a far better job of explaining it than my friend the teacher. Roger (talk) 09:46, 11 August 2011 (UTC)[reply]

It's just a matter of definition. Would you agree that, by definition, every integer is either even or odd? If it's not even then it must be odd, and if it's not odd then it must be even. If you're not happy with the explanation about why it is even, then are you suggesting that it's odd? But why is odd? You end up with a circular argument. You just have to accept the definition. An integer m is called even if it is divisible by 2, i.e. if there exists an integer n such that m = 2n. Zero is divisible by 2 because 0 = 2 × 0. In fact, zero is an interesting exception because it is divisible by any integer. — Fly by Night (talk) 21:56, 11 August 2011 (UTC)[reply]

"In fact, zero is an interesting exception because it is divisible by any integer." I think that is what confuses some people. They feel that zero is divisible by two only due to a technicality, and may thus not truly be even. This is not such a strange misunderstanding, as one is only divisible by one and itself, yet it explicitly excluded in the definition of prime numbers. -- 110.49.248.124 (talk) 14:57, 15 August 2011 (UTC)[reply]

As I understood the OP's question, the explanation given was that zero is even because it is between two odd integers, and the odd integers and even integers alternate. This describes a property of the integers without explaining WHY the integers have this property, kind of like saying that humans are mammals because we have mammary glands. It's not an appeal to authority and it's not really a tautology, although it is an immediately deducible consequence from the definition of an even number. Perhaps the OP was looking for a practical reason, as in "If zero were not even we would get the following contradiction." Since parity is a fundamental property of the integers, I don't know that a reason like this can be provided without reference to an abstract algebraic construction that does not have parity.99.100.92.26 (talk) 05:41, 12 August 2011 (UTC)[reply]

0 is even because 0 is 2 times an integer (namely, 2 times 0). Michael Hardy (talk) 16:34, 13 August 2011 (UTC)[reply]

Shape similarity?

Copied from WT:WPM.--Salix (talk): 15:46, 10 August 2011 (UTC)[reply]

From two coastline maps I want to know a value for their similarity. Problem are this maps. The one of 1531 is the dominant Antarctica shape of the 16th century. I know a long dispute whether it is by chance or not. But it always goes along very subjective identifications of similar points. Is there some mathematical theory or algorithm that can applied to this over 50 year old problem? Where should I ask? -- Portolanero (talk) 15:37, 10 August 2011 (UTC)[reply]

From a simplistic view, you can calculate how much land area is occupied by both maps versus how much is only occupied one or the other. But, when you want to measure along the coastline, you will hit the old "coastline problem", which basically says that the length of the coastline approaches infinity. So, you have to stay away from measuring along the coastline and, instead, look at the area occupied within the coastline. -- kainaw ™ 15:55, 10 August 2011 (UTC)[reply]

This looks like a question for Statistical shape analysis, or one of it variants such as Point distribution model, Procrustes analysis. Most of these techniques would involve Landmark point as references to compare the two shapes (in effect the similar points you mention) but there are some techniques which don't require such. It should be possible to come up with some measure of how similar the shapes are but construction a Null hypothesis could prove difficult.--Salix (talk): 16:08, 10 August 2011 (UTC)[reply]

I thought something along Fractal analysis or Fourier analysis of the local derivation. The coastline could be smoothed of course. But I`m no real mathematician. -- Portolanero (talk) 17:54, 10 August 2011 (UTC)[reply]

Statistics – p and α

OK, so I tried to read http://ftp.isds.duke.edu/WorkingPapers/03-26.pdf (cited in P-value), but I'm still confused about why these two are different. By way of example, here is a quote from a medical journal (PMID 7122669), explaining how a particular study found evidence of a particular remedy's effectiveness (namely, the number of subjects reporting a positive result after taking the remedy was statistically significantly higher than the number reporting success after having taken a placebo):

The frequency of better sleep quality reports with valerian is significantly higher than for placebo (p<0.05).

Then there were bar graphs than looked roughly like this (figures are rough—read off the graph):

Sleep quality – Whole population
Worse than usual Response Frequency (%)

Placebo
24

Valerian
26

Hova®
28

Sleep quality – Whole population
Better than usual Response Frequency (%)

Placebo
27

Valerian
41

Hova®
27

Now, my question is: is the article not saying that if the subjects were selecting responses at random/making it up/whatever (remembering that the trial was randomised and double-blind) the chances of so high a fraction (i.e. "this high or more") of those who reported positive effects falling into the Valerian category is less than 5%? Hence, is it not saying that the chances of a false positive are less than 5%? Ergo, what is the difference between p and α? It Is Me Here ^{t / c} 23:39, 10 August 2011 (UTC)[reply]

The article is saying that if the Valerian and placebo subjects both really have equal sleep quality on average, then the chances of seeing such a large difference in the data as observed is less than 5%. It is not saying either of the things you described. Looie496 (talk) 01:20, 11 August 2011 (UTC)[reply]

Sorry, I am still confused.

You still seem to be saying that the 5% refers to the probability of the observed results having occurred by chance. Why, then, was I wrong in my first statement: what difference does it make whether the false positive would have arisen as a result of differences between the patients' bodies or as a result of their lying on the sleep questionnaires?
In analysing and interpreting their raw data, did Leathwood et al. use Fisher philosophy or Neyman–Pearson philosophy?

1. What difference does the answer to (2) make?

It Is Me Here ^{t / c} 12:09, 11 August 2011 (UTC)[reply]

I don't understand (2) so I will only respond to (1). The null hypothesis states that the Valerian and placebo subjects have equal sleep quality. It does not assert anything about what process causes the sleep quality to be equal. It does not make any assertion about whether responses are selected at random, or made up, or any other causal thing: it only asserts that the numbers that come out are on average the same for both groups. Therefore, when the null hypothesis is rejected, the only conclusion you can draw is that something produces higher numbers for the Valerian group -- without further information you can't draw any conclusion about what it is that differs. Looie496 (talk) 23:19, 11 August 2011 (UTC)[reply]

I think the confusion is the difference between chance and variation. In this study, the mean sleep quality of the treatment group is different from that of the control group. This could mean that the treatment is effective; however, if the sleep quality has a large variance, then it's possible that the treatment makes no difference and that there was just a lot of variation in the subjects' responses. Random sampling from a distribution with a large variance will result in values far away from the mean more often than sampling from a distribution with a small variance. In random sampling, these values would be determined by chance; however, the variation in subject response (great or small) is what leads to more values far away from the mean, not chance itself. Put another way, you will get values far away from the mean by chance more often in sampling from a distribution with a large variance than a small one, but the variance is the reason for this, not chance.99.100.92.26 (talk) 06:13, 12 August 2011 (UTC)[reply]