Life In 19x19

tundra wrote:A possible solution to Problem 1, though using complex-valued functions in the complex plane:

We want f(z) + g(z) = z, where z = x + i*y, i such that i^2 = -1
i.e., x = Re(z) = the real part of z, y = Im(z) = = the imaginary part of z.

Define f(z) = f(x+i*y) = x - sin(x) + sin(y)
Note that f(z) has period d = 2*pi*i: When z changes by d, its real part, x, is unchanged, so x - sin(x) does not change either. Its imaginary part, y, changes by 2*pi, but this is just the period of sin(y). So f(z) is unchanged.

Similarly, define g(z) = g(x+i*y) = i*y + sin(x) - sin(y)
When z changes by d' = 2*pi, y is unaffected, and we just have the periodicity of sin(x).

So f and g are both periodic, with periods d = 2*pi*i and d'= 2*pi, respectively.

And when we take their sum, the sine functions all cancel, leaving us with:

f(z) + g(z) = x + i*y = z, as desired.

gaius wrote:Hehe, that's a nifty way around the real problem .

Tundra's solution (or the simplification of it) uses no special property of complex numbers. In the same way, we could construct a solution for e.g. R^2, R^5, Q^27, and all sorts of other vector spaces .

gaius wrote:Shaddy, your "proof" sounds like it comes from a textbook somewhere, but all my mathematical intuition screams that there must be a flaw in this logic. As I said before, I'm not a mathematician but a physicist - I like to think in terms of concrete stuff.

My first thought was that the whole conclusion seems to conflict with information theory; you generate information where there is none. Can you disprove this line of reasoning? Thinking further though, your "proof" does not do anything for finite sets except for the trivial observation that, with a finite set of people, the number of errors is also finite. You are not really boosting the accuracy rate, you're only making sure the amount of errors is not infinite (right?). Maybe that could lift my objection, though my math is not good enough to really be certain.

After thinking a bit more, I have far greater problems with the following paradox. You imply that, for every infinite sequence of ones and zeroes, it is possible to find a uniquely defined equivalence set. Accepting that, let's evaluate this "algorithm" (it has infinite runtime, but apparently such an algorithm is acceptable in your paradigm!):

1. Take an infinite sequence of ones and zeroes.
2. Change the first element. By definition, the resulting sequence will still be in the same equivalence set as the original one (there is only one mistake!).
3. Now, do the following: IF we are in the original equivalence set, change the next (second, third, etc.) element. ELSE, halt.
4. Repeat (3) for all elements.

Now, obviously, after repeating for all elements, the list will not be in the same equivalence set any more. Therefore, we conclude that after some number of steps (let's call it n), (3) must halt. But then, despite only having one difference, the list at step n-1 and at step n are not in the same equivalence set!

Paradox?

Bill Spight wrote:I think, as Aristotle might say, you are highlighting the difference between potential infinity and actual infinity. (IIRC, Aristotle did not think that actual infinity existed, even logically.) Normally, "for each" and "for all" mean the same thing. However, it does make a difference for step 4. I think that Aristotle would say that you must say, "Repeat (3) for each element." That leaves us in the realm of the potentially infinite. The problem has a solution only in the realm of the actually infinite.

gaius wrote:

Bill Spight wrote:I think, as Aristotle might say, you are highlighting the difference between potential infinity and actual infinity. (IIRC, Aristotle did not think that actual infinity existed, even logically.) Normally, "for each" and "for all" mean the same thing. However, it does make a difference for step 4. I think that Aristotle would say that you must say, "Repeat (3) for each element." That leaves us in the realm of the potentially infinite. The problem has a solution only in the realm of the actually infinite.

I still fail to see the difference. Of course I understand that the algorithm I posted is completely unreasonable because it will never finish, but so is the solution algorithm as it requires the construction of infinitely many "equivalence classes". However, the "solution algorithm" assumes a theoretical paradigm in which countably infinite runtimes are somehow acceptable, so I will reiterate my point. Either (a) we accept countably infinite runtimes as workeable; my algorithm will finish, and the paradox will be clear, or (b) we do not accept countably infinite runtimes, in which case the "solution algorithm" clearly does not finish, and hence, is not a valid solution to the problem. Whether we choose (a) or (b), the answer is disproved. In fact, if correct, my reasoning would disprove the existence of well-defined equivalence classes.

I realise that people smarter than me have probably considered this point too, but I would really like to hear how they came up with a workaround!

Bill, I am personally not a native English speaker, but in my vocabulary the words "each" and "all" are synonyms. As you might know, Aristotle was not an English speaker either. In fact, he spoke a strange language called Ancient Greek. Perhaps you could elaborate on the difference between these two words?

EDIT: I am not 100% sure that these runtimes are countably infinite. If not, please replace the phrase "countably infinite" by "infinite". The reasoning will be unaffected.

flOvermind wrote:Puzzle 1:
Find two periodic functions f and g, such that their sum is the identity function (that is, f(x) + g(x) = x).

DrStraw wrote:Now for the simplest answer. As the domain and range of the functions are not defined I am going to take them both as the reals modulo 1. Then f(x) = g(x) = x/2 gives the desired solution.