Wikipedia:Reference desk/Archives/Mathematics/2015 July 7

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 7

Axiom of infinity and Computer science

Our article Axiom of infinity asserts: "In...the branches of...computer science that use it, the axiom of infinity is..." etc.

I wonder, how and where - the axiom of infinity must be used by Computer science. Isn't Computer science consistent with the finitistic philosophy? HOOTmag (talk) 07:20, 7 July 2015 (UTC)

This question has been double-posted and has received some response over at WP:RDC#Computer science and Axiom of infinity., so that might be the best place to continue. -- ToE 14:09, 7 July 2015 (UTC)

It seems like an odd way to phrase the lead so maybe it should be reworded in any case. Computer Science uses infinity, at least as a limit, all the time for the analysis of algorithms. For example if you say a a sorting algorithm is O(n log n), it's really a statement about the behavior as n approaches infinity. That probably isn't a good example, so a better one is the definition of a Turing machine which assumes an infinite storage tape. Actual computers are finite but it seems more useful to model them as either being infinite or unbounded in size. --RDBury (talk) 14:36, 7 July 2015 (UTC)

Regarding the concept of Turing machine: I wonder whether it must assume the existence of an infinite storage tape. Isn't it enough to assume, that for every Turing machine which uses a given finite storage tape - one can build another Turing machine which uses a longer finite storage tape? Such a modest assumption, only assumes that no finite set contains - all Turing machines - or all finite lengths of storage tapes used by Turing machines, but this doesn't imply that there does exist an infinite set which contains - all Turing machines - or all finite lengths of storage tapes used by Turing machines.

Regarding the limit: yes, the very concept of limit - presupposed by many arguments in Computer science, must undoubtedly assume the axiom of infinity. I still wonder whether there is another usage of this axiom in Computer science. HOOTmag (talk) 17:35, 7 July 2015 (UTC)

It's an interesting question of whether Turing machines need to be infinite or just unbounded (i.e. finite but you can build a larger one if needed). For a finite Turing machine the Halting Problem is solvable; just keep track of which configurations have been seen and say the machine is in a loop if you repeat. So you at least need a sequence of larger and larger machines for the model of computation do what we expect. Lambda calculus doesn't seem to use infinity in the definition, only the assumption that an expression can have arbitrary length. I suppose you could do the same thing with a Turing machine; you only assume it's a finite tape but when the machine reaches an endpoint it automatically adds more. Effectively the same as being infinite but still finite at any given time. --RDBury (talk) 20:24, 7 July 2015 (UTC)

There's an important distinction between an infinite tape that can be in uncountably many states and a tape that can be in a countably infinite number of states. A Turing machine's tape is the latter. Normally it's restricted to contain only finitely many non-blank cells, but I suppose you could alternately restrict it to contain any computable pattern. A Turing machine with an infinite tape containing a non-computable pattern would be similar to a Turing machine with an oracle. -- BenRG (talk) 18:12, 10 July 2015 (UTC)

How to determine significance of "duo-trio" statistical test?

We are designing an experiment that needs to test two different factors. First, participants will be asked to taste two samples blind and select which one they prefer. Next, they will be given a triangular test comprised of the same to samples. They will be asked to identify the odd sample, and say whether it matched the sample that was preferred in the first experiment, or if it matches the undesirable sample. If we were to administer this test, how many people would be required to A) Take the test, and B) Identify same samples correctly, in order for the results to be significant. — Preceding unsigned comment added by 23.30.224.177 (talk) 21:42, 7 July 2015 (UTC)

Have a look at Sample_size_determination to start. SemanticMantis (talk) 23:34, 7 July 2015 (UTC)

What is "a triangular test comprised of the same to samples" ? Bo Jacoby (talk) 08:08, 8 July 2015 (UTC).

I presume the OP meant "the same two samples". In this case, we can also presume they mean that they will be given three samples to test from the same two originals: there are therefore two the same.--Phil Holmes (talk) 08:49, 8 July 2015 (UTC)

Thanks. That makes sense. So first the substances A and B are tasted and, say, B is preferred. Secondly AAB or ABB are tasted and the "odd sample", (that is B if AAB and A if ABB), is determined. The answer may be correct (=1) or incorrect (=0). Assume that the procedure is done n times and the correct answer is given k times and so the incorrect answer is given n–k times. Now what "result" are we talking about? Bo Jacoby (talk) 09:50, 8 July 2015 (UTC).