Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Julia Robinson helped define the limits of mathematical knowledge (2019)

sciencenews.org

Post reply on HN
Print view View original

11–19 of 19 posts

Re: Julia Robinson helped define the limits of mathematical knowledge (2019)

#11

Post by najdan33 »

ykonstant wrote: post #8
aleks224 wrote: post #3

Earlier quoted context omitted.

The undecidability property proven here doesn't imply that there exists at least one Diophantine equation for which we'll never know if it's solvable or not, does it?

In [0], Carl and Moroz give an explicit polynomial in 3639528+1 variables such that: a well-formed formula is a theorem in the first order predicate calculus if and only if the polynomial parametrized by the Diophantine coding of the formula (a single natural number) has a solution in N^{3639528}. From this, they get an explicit Diophantine equation such that: the Godel-Bernays set theory is consistent if and only if…

Does there exist a set of yes/no problems such that:

- there's no general algorithm that can solve an arbitrary problem from the set (the whole thing is undecidable)

- each problem in isolation _can_ be solved. there's no single problem that's impossible to solve

Re: Julia Robinson helped define the limits of mathematical knowledge (2019)

#12

Post by layer8 »

najdan33 wrote: post #11
ykonstant wrote: post #8

Earlier quoted context omitted.

In [0], Carl and Moroz give an explicit polynomial in 3639528+1 variables such that: a well-formed formula is a theorem in the first order predicate calculus if and only if the polynomial parametrized by the Diophantine coding of the formula (a single natural number) has a solution in N^{3639528}. From this, they get an explicit Diophantine equation such that: the Godel-Bernays set theory is consistent if and only if…

Does there exist a set of yes/no problems such that: - there's no general algorithm that can solve an arbitrary problem from the set (the whole thing is undecidable) - each problem in isolation _can_ be solved. there's no single problem that's impossible to solve

I don’t think so, at least if you assume that each concrete solution can be expressed in finite length in a formal language with a finite alphabet, and can be mechanically checked (which is generally the case for mathematical proofs). Because then you could just enumerate all strings of that language until you find one that describes the solution to the given problem, which by your second item would be guaranteed to exist, and thus the procedure be guaranteed to terminate, contradicting your first item.

Re: Julia Robinson helped define the limits of mathematical knowledge (2019)

#13

Post by layer8 »

hackandthink wrote: post #5
aleks224 wrote: post #3

Earlier quoted context omitted.

The undecidability property proven here doesn't imply that there exists at least one Diophantine equation for which we'll never know if it's solvable or not, does it?

My understanding: There's no algorithm to decide. But for any equation we can be lucky to find a solution or a proof that there's no solution. But this doesn't prove that there is an equation for which we'll never know if it's solvable or not.

See https://news.ycombinator.com/item?id=34384838, I think it disproves your last sentence — at least when assuming that all solutions and all proofs of non-existence of a solution are expressible in a shared formal language.

Re: Julia Robinson helped define the limits of mathematical knowledge (2019)

#14

Post by moloch-hai »

I would have liked for the story to have noted, at least in passing, that 3³+4³+5³ = 6³.

(I found this in the brilliantly mad "The celestial inspirations for Giza, Stonehenge and Washington D.C." by Robin Spivey:

https://www.researchgate.net/profile/Robin-Spivey-2/publicat...

Along with that, the Great Pyramid's latitude in degrees matches, to 6 digits, the speed of light in m/s divided by 10000; the King's chamber is precisely 5π/3 and also 2φ² meters wide; and that latitude in radians is π/6. Suffice to say that numerical coincidences everywhere are more the norm than the exception.)

Re: Julia Robinson helped define the limits of mathematical knowledge (2019)

#15

Post by ykonstant »

najdan33 wrote: post #11
ykonstant wrote: post #8

Earlier quoted context omitted.

In [0], Carl and Moroz give an explicit polynomial in 3639528+1 variables such that: a well-formed formula is a theorem in the first order predicate calculus if and only if the polynomial parametrized by the Diophantine coding of the formula (a single natural number) has a solution in N^{3639528}. From this, they get an explicit Diophantine equation such that: the Godel-Bernays set theory is consistent if and only if…

Does there exist a set of yes/no problems such that: - there's no general algorithm that can solve an arbitrary problem from the set (the whole thing is undecidable) - each problem in isolation _can_ be solved. there's no single problem that's impossible to solve

The way you are phrasing your question is confusing; without the parenthesis, your two statements are identical. The only meaningful way to interpret "The whole thing is undecidable" is whether you can or cannot decide all (infinitely many) statements at once.

If that is what you mean, then yes: take any undecidable Diophantine equation Q=0 of, say, n variables. Consider the sequence of yes/no problems P_K = {Is there a solution to Q=0 in [-K,K]^n?} parametrized by a positive integer K. Each of those problems is decidable in isolation, but the totality cannot be, since that would decide if Q=0 has a solution or not.

Re: Julia Robinson helped define the limits of mathematical knowledge (2019)

#16

Post by najdan33 »

layer8 wrote: post #12
najdan33 wrote: post #11

Earlier quoted context omitted.

Does there exist a set of yes/no problems such that: - there's no general algorithm that can solve an arbitrary problem from the set (the whole thing is undecidable) - each problem in isolation _can_ be solved. there's no single problem that's impossible to solve

I don’t think so, at least if you assume that each concrete solution can be expressed in finite length in a formal language with a finite alphabet, and can be mechanically checked (which is generally the case for mathematical proofs). Because then you could just enumerate all strings of that language until you find one that describes the solution to the given problem, which by your second item would be guaranteed to…

Thanks for the answer, it helps piece together the puzzle. I believe there's a problem with this reasoning:

> each concrete solution can be expressed in finite length in a formal language with a finite alphabet

Suppose that's the case, the problem is that the resulting language of all the finite proofs can still be infinite and we again cannot enumerate and check all the solutions (since the final set is infinite). Therefore we're short of a method to decide yes/no for each question.

This appears to be exactly the case in the example provided by @ykonstant

> Consider the sequence of yes/no problems P_K = {Is there a solution to Q=0 in [-K,K]^n?} parametrized by a positive integer K.

For each yes/no question, the workload is finite, but for the union of all yes/no questions, the workload is not finite.

Re: Julia Robinson helped define the limits of mathematical knowledge (2019)

#17

Post by najdan33 »

ykonstant wrote: post #15
najdan33 wrote: post #11

Earlier quoted context omitted.

Does there exist a set of yes/no problems such that: - there's no general algorithm that can solve an arbitrary problem from the set (the whole thing is undecidable) - each problem in isolation _can_ be solved. there's no single problem that's impossible to solve

The way you are phrasing your question is confusing; without the parenthesis, your two statements are identical. The only meaningful way to interpret "The whole thing is undecidable" is whether you can or cannot decide all (infinitely many) statements at once. If that is what you mean, then yes: take any undecidable Diophantine equation Q=0 of, say, n variables. Consider the sequence of yes/no problems P_K = {Is ther…

Thank you for suggesting this example.

For the undecidable Diophantine equation Q=0 of n variables - I'm assuming that the fact that someone could hit a solution randomly (by randomly generating the n variables and getting lucky) does not contradict with its undecidability.

Still I'm not clear what happens if such a solution would be randomly hit for an equation that's mapped to another hard question such as ZFC consistency. It would imply that a question such as ZFC consistency could be solved by randomly generating an answer, which seemingly doesn't make sense?

Re: Julia Robinson helped define the limits of mathematical knowledge (2019)

#18

Post by layer8 »

najdan33 wrote: post #16
layer8 wrote: post #12

Earlier quoted context omitted.

I don’t think so, at least if you assume that each concrete solution can be expressed in finite length in a formal language with a finite alphabet, and can be mechanically checked (which is generally the case for mathematical proofs). Because then you could just enumerate all strings of that language until you find one that describes the solution to the given problem, which by your second item would be guaranteed to…

Thanks for the answer, it helps piece together the puzzle. I believe there's a problem with this reasoning: > each concrete solution can be expressed in finite length in a formal language with a finite alphabet Suppose that's the case, the problem is that the resulting language of all the finite proofs can still be infinite and we again cannot enumerate and check all the solutions (since the final set is infinite). T…

> Suppose that's the case, the problem is that the resulting language of all the finite proofs can still be infinite and we again cannot enumerate and check all the solutions (since the final set is infinite).

The set of all strings in the language is only countably infinite (= same size as tne natural numbers), which means you will reach the solution string after a finite time (just count 1, 2, 3, ... until you reach the corresponding natural number).

What I'm saying is that if each individual problem has a solution in the form of an individual finite proof (the premise of your second point), then the above gives you a general algorithm for finding the proof for any given of those individual problems (contradicting the premise of your first point).

What this doesn't give you is a way to prove that a proof exists for all individual prohlems, because that indeed would take infinite time.

Ykonstant is correct in that your use of "undecidable" was confused; I just ignored that.

Re: Julia Robinson helped define the limits of mathematical knowledge (2019)

#19

Post by najdan33 »

layer8 wrote: post #18
najdan33 wrote: post #16

Earlier quoted context omitted.

Thanks for the answer, it helps piece together the puzzle. I believe there's a problem with this reasoning: > each concrete solution can be expressed in finite length in a formal language with a finite alphabet Suppose that's the case, the problem is that the resulting language of all the finite proofs can still be infinite and we again cannot enumerate and check all the solutions (since the final set is infinite). T…

> Suppose that's the case, the problem is that the resulting language of all the finite proofs can still be infinite and we again cannot enumerate and check all the solutions (since the final set is infinite). The set of all strings in the language is only countably infinite (= same size as tne natural numbers), which means you will reach the solution string after a finite time (just count 1, 2, 3, ... until you reac…

You are right, I was wrong. If there's a way to evaluate each single yes/no question in a finite number of steps, then the set of all problems is decidable, since any question can be resolved in a finite number of steps.

That would seem to imply that each problem (seen as a set of sub-problems) contains some undecidable sub-problems.. so is there something like the most primitive undecidable problem..

Post reply on HN