5 ms·

My mathematical logic is rusty, but if I recall correctly, Gödel's incompleteness theorem basically states that it is impossible to solve this kind of question.

My mathematical logic is rusty, but if I recall correctly, Gödel's incompleteness theorem basically states that it is impossible to solve this kind of question. No matter how many tests you run, there will always be an uncertainty. An incredibly stupid example is that the rule could be "yes for strictly increasing, OR if one of the numbers is -18273192783127897981." You'll never know. I understand this is contrived, especially when the test subject doesn't know. But if you do realize this while doing it, it makes the test a little frustrating.. EDIT: I see people are making a connection with unit testing, and the irony is poetic. This is precisely the problem Dijkstra was talking about when he said that "Testing shows the presence, not the absence of bugs."

the_af 11y ago
It's not ironic. Dijkstra's assertion is, in a convoluted way, related to the main point of the quiz and the article :)
monjaro 11y ago
This has nothing to do with Gödel's incompleteness theorem. It's much simpler than that: https://en.wikipedia.org/wiki/Wittgenstein_on_Rules_and_Private_Language#The_rule-following_paradox https://en.wikipedia.org/wiki/Wittgenstein_on_Rules_and_Priv...
- GhotiFish 11y ago
  Thanks for the link! That was an interesting read, but I don't think I understand the premise of the argument. From the article ... It is perfectly consistent with your previous use of 'plus' that you actually meant it to mean the 'quus' function, ... That may be true, but only if you assume I'm not referring to the plus derived from the axioms of principa mathematica. I am. Is it then the question that when I refer to the principa mathematica that I'm actually referring to principa quus? If I then describe axiom 1 can you not know my words are referring to axiom quus? It seems the only power of this assertion is that language provides no absolute common ground. Am I understanding this correctly?
  - Matumio 11y ago
    This makes my head hurt. Surely Wittgenstein had permission to use Occam's razor? I mean, if it's possible that you actually meant quus_5 then it's equally possible that you meant quus_3 or quus_114, but since you didn't mention that, I will just assume you meant whichever requires the least amount of parameter-guessing from my side. After all, you have written it down for a human receiver, not for an alien from the Quus_8th dimension.
scarmig 11y ago
Remotely related: I've been interested for awhile in how the same initial terms of a sequence could possibly be generated by multiple rules. For example, you might have 2,3... And the rest of the sequence might look like either 2,3,4,5,6... or 2,3,5,8,13... or 2,3,5,7,11... or even 2,3,5,10,20... Clearly, on some level those sequences are all much less complicated than one defined as "The first term is 2, the second term is 3, the third term is 919243, the fourth term is -1234..." It's unclear to me how one might rank them in complexity, though. The maximum amount of memory necessary to get an arbitrary nth term? The number of operations necessary to get to the next term? Another interesting question to me: if there is an ordering of ways to generate a sequence of numbers, given the first couple terms of a sequence of numbers, what are the simplest N ways to generate the full sequence?
- liadmat 11y ago
  Take a look at Kolmogorov complexity. It's uncomputable.
- nsrivast 11y ago
  I think you might enjoy the book Fluid Concepts and Creative Analogies, by Douglas Hofstadter [1]. The first chapter is on (what Hofstadter argues is) the fundamental nature of recognizing patterns in number sequences. [1] http://www.amazon.com/Fluid-Concepts-And-Creative-Analogies/dp/0465024750 http://www.amazon.com/Fluid-Concepts-And-Creative-Analogies/...
- drewcrawford 11y ago
  Fun fact: Mathemetica has a method FindSequenceFunction which does exactly what you describe. In my experience, however, it generally requires at least 4 terms. I'm not totally sure how the math behind it works (maybe it's similar to Eureqa?) but the results speak for themselves and are rather incredible. For example, if I run FindSequenceFunction on this input: {0, 1, 3, 8, 19, 43, 94, 201, 423, 880} Which is the number of 0,1 sequences of length n that contain two adjacent 1s Mathematica produces the result: 1/10 (5 2^(1 + x) - 5 (1/2 - Sqrt[5]/2)^x + 3 Sqrt[5] (1/2 - Sqrt[5]/2)^x - 5 (1/2 + Sqrt[5]/2)^x - 3 Sqrt[5] (1/2 + Sqrt[5]/2)^x) Which, astonishingly, is correct for all the values I've tried. So apparently Mathematica understands more about this sequence than I do, and I know its definition. Another party trick is to use the input {-(1/6), 2/15, -(13/140), 23/315, -(83/1386), 305/6006, -(2269/ 51480), 4259/109395, -(16103/461890), 30616/969969} Which is the integral x^n (1 - 2 x)^n for x from 0 to 1, for n = 0..<10. Here it seems 10 numbers are required. This yields the solution (2^(-2 - 3 x) x! (Sqrt[\[Pi]] (1 + x)! + 3 (-1)^x 2^( 2 + 3 x) (1/2 (1 + 2 x))! Hypergeometric2F1[1, 3/2 + x, 2 + x, -8]))/((1/2 + x)! (1 + x)!) Which as far as I can tell, is a closed-form solution (!) to the integral. A solution it worked out to an integral it has never seen, but only the first 10 elements in the sequence. So it's safe to say Mathematica knows a lot more about math than I do.
xenophon 11y ago
I think the core idea is much simpler than that. It's the notion that falsifiability is the most powerful tool in our arsenal when we try to conceive of theories that explain a certain state of affairs. The idea you're getting at is that no number of confirming observations can verify a universal generalization -- the reason why we continue to call generally accepted "truths" theories. But we can increase our certainty to the greatest degree possible by trying to test our hypothesis to the greatest degree we can.
deleted 11y ago
[deleted]
yvsong 11y ago
With an equal protection clause, i.e., no particular number or a group of numbers can appear in the rule, is the problem solvable?
- eru 11y ago
  Depends on what rules you allow. What you want to forbid is not so much mentioning specific numbers, but you want to only allow rules that have certain symmetries. Eg you can require tranlation invariance rule(x, y, z) = rule(x+offset, y+offset, z+offset) to restrict the set of rules.
odonnellryan 11y ago
Tests like this are frustrating even if you don't recognize the logical fallacy! Just because it's always possible you're wrong. You're either right because you're lucky, or wrong because you messed up!
nightcracker 11y ago
This does not hold - the test uses Javascript's numbers, which are finite. So it's theoretically possible to test every combination of inputs and convincingly answer what a possible rule is.

the_af 11y ago

It's not ironic. Dijkstra's assertion is, in a convoluted way, related to the main point of the quiz and the article :)

monjaro 11y ago

This has nothing to do with Gödel's incompleteness theorem. It's much simpler than that: https://en.wikipedia.org/wiki/Wittgenstein_on_Rules_and_Private_Language#The_rule-following_paradox https://en.wikipedia.org/wiki/Wittgenstein_on_Rules_and_Priv...

GhotiFish 11y ago
Thanks for the link! That was an interesting read, but I don't think I understand the premise of the argument. From the article ... It is perfectly consistent with your previous use of 'plus' that you actually meant it to mean the 'quus' function, ... That may be true, but only if you assume I'm not referring to the plus derived from the axioms of principa mathematica. I am. Is it then the question that when I refer to the principa mathematica that I'm actually referring to principa quus? If I then describe axiom 1 can you not know my words are referring to axiom quus? It seems the only power of this assertion is that language provides no absolute common ground. Am I understanding this correctly?
- Matumio 11y ago
  This makes my head hurt. Surely Wittgenstein had permission to use Occam's razor? I mean, if it's possible that you actually meant quus_5 then it's equally possible that you meant quus_3 or quus_114, but since you didn't mention that, I will just assume you meant whichever requires the least amount of parameter-guessing from my side. After all, you have written it down for a human receiver, not for an alien from the Quus_8th dimension.

scarmig 11y ago

Remotely related: I've been interested for awhile in how the same initial terms of a sequence could possibly be generated by multiple rules. For example, you might have 2,3... And the rest of the sequence might look like either 2,3,4,5,6... or 2,3,5,8,13... or 2,3,5,7,11... or even 2,3,5,10,20... Clearly, on some level those sequences are all much less complicated than one defined as "The first term is 2, the second term is 3, the third term is 919243, the fourth term is -1234..." It's unclear to me how one might rank them in complexity, though. The maximum amount of memory necessary to get an arbitrary nth term? The number of operations necessary to get to the next term? Another interesting question to me: if there is an ordering of ways to generate a sequence of numbers, given the first couple terms of a sequence of numbers, what are the simplest N ways to generate the full sequence?

liadmat 11y ago
Take a look at Kolmogorov complexity. It's uncomputable.
nsrivast 11y ago
I think you might enjoy the book Fluid Concepts and Creative Analogies, by Douglas Hofstadter [1]. The first chapter is on (what Hofstadter argues is) the fundamental nature of recognizing patterns in number sequences. [1] http://www.amazon.com/Fluid-Concepts-And-Creative-Analogies/dp/0465024750 http://www.amazon.com/Fluid-Concepts-And-Creative-Analogies/...
drewcrawford 11y ago
Fun fact: Mathemetica has a method FindSequenceFunction which does exactly what you describe. In my experience, however, it generally requires at least 4 terms. I'm not totally sure how the math behind it works (maybe it's similar to Eureqa?) but the results speak for themselves and are rather incredible. For example, if I run FindSequenceFunction on this input: {0, 1, 3, 8, 19, 43, 94, 201, 423, 880} Which is the number of 0,1 sequences of length n that contain two adjacent 1s Mathematica produces the result: 1/10 (5 2^(1 + x) - 5 (1/2 - Sqrt[5]/2)^x + 3 Sqrt[5] (1/2 - Sqrt[5]/2)^x - 5 (1/2 + Sqrt[5]/2)^x - 3 Sqrt[5] (1/2 + Sqrt[5]/2)^x) Which, astonishingly, is correct for all the values I've tried. So apparently Mathematica understands more about this sequence than I do, and I know its definition. Another party trick is to use the input {-(1/6), 2/15, -(13/140), 23/315, -(83/1386), 305/6006, -(2269/ 51480), 4259/109395, -(16103/461890), 30616/969969} Which is the integral x^n (1 - 2 x)^n for x from 0 to 1, for n = 0..<10. Here it seems 10 numbers are required. This yields the solution (2^(-2 - 3 x) x! (Sqrt[\[Pi]] (1 + x)! + 3 (-1)^x 2^( 2 + 3 x) (1/2 (1 + 2 x))! Hypergeometric2F1[1, 3/2 + x, 2 + x, -8]))/((1/2 + x)! (1 + x)!) Which as far as I can tell, is a closed-form solution (!) to the integral. A solution it worked out to an integral it has never seen, but only the first 10 elements in the sequence. So it's safe to say Mathematica knows a lot more about math than I do.

xenophon 11y ago

I think the core idea is much simpler than that. It's the notion that falsifiability is the most powerful tool in our arsenal when we try to conceive of theories that explain a certain state of affairs. The idea you're getting at is that no number of confirming observations can verify a universal generalization -- the reason why we continue to call generally accepted "truths" theories. But we can increase our certainty to the greatest degree possible by trying to test our hypothesis to the greatest degree we can.

deleted 11y ago

[deleted]

yvsong 11y ago

With an equal protection clause, i.e., no particular number or a group of numbers can appear in the rule, is the problem solvable?

eru 11y ago
Depends on what rules you allow. What you want to forbid is not so much mentioning specific numbers, but you want to only allow rules that have certain symmetries. Eg you can require tranlation invariance rule(x, y, z) = rule(x+offset, y+offset, z+offset) to restrict the set of rules.

odonnellryan 11y ago

Tests like this are frustrating even if you don't recognize the logical fallacy! Just because it's always possible you're wrong. You're either right because you're lucky, or wrong because you messed up!

nightcracker 11y ago

This does not hold - the test uses Javascript's numbers, which are finite. So it's theoretically possible to test every combination of inputs and convincingly answer what a possible rule is.