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

Re:Julia Robinson helped define the limits of mathematical k... by najdan33 on Sunday January 15, 2023 @08:28AM (#34389243)

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.

[ Parent | on HN ]

Re:Julia Robinson helped define the limits of mathematical k... by layer8 on Sunday January 15, 2023 @10:33AM (#34390106)

> 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 @ykonstant saying is something different: They want to solve all infinitely many single problems. That may not be possible to do in finite time. But each individual one may be solvable in finite time, which is the question you were asking.

[ Parent | on HN ]

Re:Julia Robinson helped define the limits of mathematical k... by najdan33 on Sunday January 15, 2023 @12:07PM (#34390947)

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..

[ Parent | on HN ]