Wikipedia:Reference desk/Archives/Mathematics/2012 April 15

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.

April 15

The algebraic closure of Z2

Is there any interesting topology on the algebraic closure of Z2? (interesting means that it is Hausdorff space, addition, multiplication, invention are continuous, and the topology is not the discrete topology)--84.229.208.77 (talk) 13:35, 15 April 2012 (UTC)

There is the Zariski topology, although it's a bit boring in this case, and not Hausdorff. The closed sets are the whole field and all finite sets. It satisfy the other properties you mentioned. Rckrone (talk) 14:23, 15 April 2012 (UTC)

biggest number proposal

could someone address my contribution for biggest number (the one labelled "contribution" under new subsection on this page, but without any answers). perhaps something I wrote was unclear or ambiguous? (I only left out the minor detail of the exact instruction set the hypothetical computers would use, but you can substitute a simple turing machine tape and all, since it's a description of a number, not instructions for what to actually do. It only has to be unambiguous, not calculable in the here and now.) --80.99.254.208 (talk) 18:07, 15 April 2012 (UTC)

What do you mean by "computes the value of every number up to that prime"? Staecker (talk) 02:26, 16 April 2012 (UTC)

Sorry, earlier I said that by "computes a value of a number" it means interpreting that number as binary and simply executing it, sucht hat "computes the value of a number" means evaluate that number to either the output of the program it represents as binary, or to nothing otherwise. The one implementation detail I left out is the exact theoretical architecture and instruction set the binary is supposed to run on, but this is trivial and al turing-complete computers would be equivalent in this respect. --84.1.177.43 (talk) 10:18, 16 April 2012 (UTC)

What you wrote is not very easy to decode, unfortunately. However, I don't think it would work out very well since some of the computations would never halt; I know you said something about infinite time and space, but if you have this at your disposal, it kind of defeats the whole point (unless you are talking potentially infinite, but why point it out then?) At any rate, I'd be willing to look at your contribution if you laid it out more clearly. Phoenixia1177 (talk) 20:21, 16 April 2012 (UTC)

Thank you. The ones that never halt are not counted as a result. Here's a go at a cleaner layout:

Goal: To DESCRIBE a finite number such that the description is unambiguous. We do not have to actually be able to compute it, nor does the description have to be finite in any sense except for fitting below and being mathematically unambiguous. (See http://web.mit.edu/arayo/www/bignums.html for rules - Any unusual notation must be explained to the audience. and "Primitive semantic vocabulary is not allowed. (This means that entries like `the smallest number bigger than any number named by a human so far' or `the smallest number that cannot be named in less than fourteen English words' are invalid).")

The basic rules is "Contestants take turns writing down expressions denoting natural numbers". Thus the below must simply denote a natural number. It does not have to be a computable expression in a finite sense.

Rule: Computer a and computer b (c is the same) are capable of infinite space and infinite time calculations.

Operation of a and b (and c): For every INPUT - denoted n - that a or b receives, it performs the following operations: - For each natural number i from 0 to n, it evaluates the result by running the "number" as a binary program (i expressed as binary), this result will be: malformed program, does not terminate, or output. Keeping track of these results for each i, the OUTPUT is the largest of them that is finite.

With this mode of operation in mind, the following algorithm denotes the largest integer I can name.

1. A's input is the first prime greater than googleplex. Its output is given to B as B's next input. 2. B's output is given to A as A's next input. This is repeated, with the addition, as soon as both A and B have produced their first output, that at every point an output is returned to the other computer, C takes the last two outputs, multiplies them together to produce MULTNUM, and uses the new number as it's input. (remember, c operates just like a and b).

We repeat the above until the output of c is finite and ends with the last output appended to the input that produced it in binary. This number is the integer that is denoted by the present description.

SIMPLIFIED EXAMPLE

To show you the algorithm in action, let's step through it with this simple "instruction set". Evaluating a binary program is done by simply outputing it if it does not begin with a binary11, or outputing anything after the 11 twice if it does. Instead of starting with the first prime greater than googleplex, a will start with 7. A: (b and c have no input yet). Input: 7. Runs, 1,2,3,4,5,6,7 all as binary. Results: 1 (binary '1'): 1
2 (binary '10'): 10
3 (binary '11'): no output
4 (binary '100'): 100
5 (binary '101'): 101
6 (binary '110'): 00
7 (binary '111'): 1111

largest output: 1111 (decimal 15). This is the output of A for the input 7.

B: (c has no input yet). Is given 15, and does the same as the above for all programs 1 through 1111.

C: after B has its output, the last input (15) is multiplied by the last output (not computed here), and C does the same algorithm. If the resulting largest number ends with 1111 followed by whatever the output of this number is given to B is, then the program ends and this number is the result. Otherwise, the output is given to A as input and we continue...

This is an absurd simplification, of cousre, since we're not using a real programming language, but instead (output the whole program unless it starts with 11, in which case output the rest of it twice). In the actual example, we would be uising a turing-complete instruction set (The exact one doesn't matter, they're all equivalent, I don't want to bother wiht having to specify one here).

So now you see my algorithm, and how it describes a single integer. What do you think? --80.99.254.208 (talk) 08:56, 17 April 2012 (UTC)Italic text

Thank you for specifying:-) Honestly, I'm still a little confused; also, I'm not seeing why this would always halt, it seems likes you could always get an output from c that forces it all to repeat over and over and over. Moreover, though, I'm a little confused at the point of all this, are we just looking for ways to specify big numbers or are we interested in comparing the various entries with proofs of which wins? On that topic, though, if you lose (with your method say), why not just take the result of you method and, then, use that as input for the same process again, surely enough of this will net you a win; so are we looking at growth rate of a method or the size given inputs? Also, just curious, why are you using the smallest prime greater than a googolplex? Why not just a googolplex? Not trying to sound bitchy, or condescending, I'm just not getting what we're trying to do and what conditions entail that we've done it. Thanks :-) Phoenixia1177 (talk) 09:37, 17 April 2012 (UTC)

Inequalities

Hi all. Basically, I need to come up with a logical expression that will cause an algorithm to iterate until exactly one of two inequalities is satisfied. Let these inequalities be a<b<c, inequality A, and x<y<z, inequality B, (bear in mind that precisely one of these will be satisfied at a time; not both). Now I basically want to say "while A is not true or B is not true" and then have the algorithm terminate when one of them becomes true. My problem is that I don't know how to 'phrase' this in a logical fashion, i.e. mathematically. Has anyone any ideas, as I'm worried that simply saying, for example "while c<b<a or z<y<x" won't give me what I want. Thanks. meromorphic [talk to me] 19:52, 15 April 2012 (UTC)

It would help to know which computer language you are using, but here it is in FORTRAN:

     IF    ((.NOT. ((a .LT. b) .AND. (b .LT. c)))
       .OR. (.NOT. ((x .LT. y) .AND. (y .LT. z)))) THEN ...

Now this is a regular "or", but it sounds like you want an "exclusive or". If your language lacks syntax for XOR, you can do it the hard way:

     count = 0
     IF (.NOT. ((a .LT. b) .AND. (b .LT. c))) count = count + 1
     IF (.NOT. ((x .LT. y) .AND. (y .LT. z))) count = count + 1
     IF (count .EQ. 1) THEN ...

You could also make an even longer and uglier compound IF clause, but that would be even worse. StuRat (talk) 20:11, 15 April 2012 (UTC)

Thanks StuRat, that looks very helpful. I am working in Matlab, which does have xor capabilities. On the off chance that you're familiar with Matlab code, which of the following is best?

     while ((not(a<b) || not(b<c)) || (not(x<y) || not(y<z)))

     while ( (not((a<b) & (b<c))) || (not((x<y) & (y<z))))

I have used neither & nor || before (never mind inside a while loop) and am unsure of which is the better choice. Thanks for your help. meromorphic [talk to me] 21:42, 15 April 2012 (UTC)

The 2nd one looks simpler, to me. However, isn't "||" just OR, not XOR ? Do you want XOR ? If so, what's the syntax for that in Matlab ? StuRat (talk) 22:00, 15 April 2012 (UTC)

It's unclear to me whether the OP wants XOR or just regular OR. When you say "precisely one of these will be satisfied at a time; not both" do you mean it's impossible for both to be satisfied? If so then you don't need to check for that. You can just check if at least one is satisfied, and then OR will do. Rckrone (talk) 22:03, 15 April 2012 (UTC)

I looked up the XOR syntax in Matlab, and it looks like this:

while (xor (not( (a<b) & (b<c) ), not( (x<y) & (y<z) ) ) )

StuRat (talk) 22:13, 15 April 2012 (UTC)

Thank you both, I have managed to solve my problem thanks to your helpful suggestions. Just for posterity, the two inequalities could not be satisfied simultaneously and the reason my suggestions did not include reference to XOR is because I had never used it before and I thought that what I wrote would be all I needed. Thanks again. meromorphic [talk to me] 10:34, 16 April 2012 (UTC)

You're quite welcome, glad we could help. I will mark this Q resolved. StuRat (talk) 15:21, 16 April 2012 (UTC)

Possibly there are some languages missing the XOR operator, but allowing to compare logical values. In such case one can make use of the fact the logical expression can have only one of TWO values (so two expressions are different iff exactly one of them is true), and just utilize the 'is equal' operator. --CiaPan (talk) 15:29, 17 April 2012 (UTC)

Resolved

Hiring k secretaries

Question inspired by The Voice UK. What is the solution to the secretary problem if we want to hire k of the n applicants? Thanks! 77.97.198.48 (talk) 21:50, 15 April 2012 (UTC)

Intuitively I guess that similar to the usual secretary problem you would reject everyone for some training period (but shorter, depending on k), and then after that accept everyone better than the training set. But maybe there should be some adjustment process if it looks like you're being too selective or not selective enough? I'm just shooting from the hip here since no one seems to have anything concrete to say so far. Rckrone (talk) 01:14, 18 April 2012 (UTC)