[FOM] 772: Algorithmic Unsolvability 3
Harvey Friedman
hmflogic at gmail.com
Thu Oct 19 02:41:32 EDT 2017
COPING WITH ALGORITHMIC UNSOLVABILITY
As you can see, I have been emphasizing a kind of cousin relationship
between ALGORITHMIC UNSOLVABILITY and INCOMPLETENESS.
In INCOMPLETENESS, we know quite well how we cope with incompleteness.
Namely, we prove or refute the examples in question using more axioms.
In the case of CMI = concrete mathematical incompleteness, this means
that we prove the examples in question using large cardinals.
I.e., we cope with some Incompleteness with some Completeness!
This way of coping has been only partially successful in the realm of
NONCONCRETE MATHEMATICAL INCOMPLETENESS. Very successful in the realm
of the projective sets, not yet successful in the realm of
unrestricted uncountable sets, in particular with the continuum
hypothesis. Although there is a big success via the normally debunked
V = L. There is another side of V = L, not as an axiom, but as a way
of clarifying or restricting the notion of set with the idea that the
usual notion is too vague, and thereby vastly cutting out enormous
regions of nonconcrete Incompleteness. This is also largely debunked
for the obvious reason of cutting out a lot of admired work. Of
course, the restriction to L or using V = L does nothing at all to
cure CMI. At present, the only way to cure CMI is of course through
various sizes of large cardinals.
Back to ALGORITHMIC UNSOLVABILITY. The corresponding method of coping
would be this: cope with some Algorithmic Unsolvability with some
Algorithmic Solvability!
But what could this really mean?
An algorithmic unsolvability result most commonly takes the form that
a certain interesting set S of mathematical objects is not recursive.
PLAN: To show that "S intersect the set of all objects of small
complexity" is solvable!
Since we usually intend that there be only finitely many objects of
any given complexity is finite, and every finite set is solvable,
isn't this PLAN nonsense?
So WHAT does it mean that a nicely presented finite set S be SOLVABLE?
We offer two definitions, one very sharp, and the other reasonably
robust.
For definiteness, let us assume that S is a finite set of finite
strings in 100 letters, each string of length at most 1000. For some
applications of these ideas, we may want to relax this assumption, but
not for a while. I.e., S containedin {a_1,...,a_100}^1000.
ZFC SOLVABLE. Such an S is ZFC solvable if and only if for all x in
{a_1,...,a_100}^1000, the statement "x in S" is provable or refutable
in ZFC.
PROGRAM SOLVABLE. Such an S is program solvable if and only if there
is a C program that decides membership in S, of length at most 1M.
REALLY SOLVABLE. Such an S is really solvable if and only if there is
a C program that decides membership in S, of length at most 1M, where
the program halts in at most 1T steps at any given input from
{a_1,...,a_100}^1000.
Define S[i] to be the set of all elements of S of length at most i,
where 1 <= i <= 1000.
HOW DO WE COPE? So we can take practically ANY set of finitely
mathematical objects, regardless of whether we know it is recursive or
not, and ask whether S[i] is ZFC solvable, program solvable, really
solvable, and the like, starting with i = 1 and moving up - probably
moving up quite slowly.
CONJECTURE 1. This brings to life every single one of the situations
where we find ALGORITHMIC UNSOLVABILITY, across the entire
mathematical landscape. That is, it brings it all to life in an
interesting way, where civilization can reach its own level, which,
generally, may be with rather modest i.
CONJECTURE 2. In all cases (with unsolvability), when pushing i up
incrementally, new interesting mathematical challenges of independent
interest need to be met to support the progress.
Note that this point of view has been applied to the original
algorithmic unsolvability - the HALTING PROBLEM. This point of view,
with some consolidation, led to what is called the BUSY BEAVER
PROBLEM, or the BB function. A fixed hard nosed presentation of TMs
was fine tuned for this purpose - two tape symbols, two way infinite,
partial function from state, symbol into state, left/right.
It makes sense to similarly consolidate in some appropriate manner
connected with the context, upon considering S[1],S[2],S[3],S[4],... .
But it is I think very good to have a uniform approach that cuts
across virtually all mathematical situations.
THEOREM. Let S be algorithmically unsolvable. There is a least i >= 0
such that S[i] is not ZFC solvable.
CONJECTURE 3. Let S be natural and algorithmically unsolvable. Let i
be least such that S[i] is not ZFC solvable. Then S[i] is ZFC*
solvable, where ZFC* is ZFC + some small large cardinals. As i is
raised incrementally, we climb the large cardinal hierarchy in the
appropriate sense. At some not too far place, we outrun the large
cardinal hierarchy, and descend into LOGICAL CHAOS. Logical Chaos has
some interesting robust definition.
************************************************************************
My website is at https://u.osu.edu/friedman.8/ and my youtube site is at
https://www.youtube.com/channel/UCdRdeExwKiWndBl4YOxBTEQ
This is the 772nd in a series of self contained numbered
postings to FOM covering a wide range of topics in f.o.m. The list of
previous numbered postings #1-699 can be found at
http://u.osu.edu/friedman.8/foundational-adventures/fom-email-list/
700: Large Cardinals and Continuations/14 8/1/16 11:01AM
701: Extending Functions/1 8/10/16 10:02AM
702: Large Cardinals and Continuations/15 8/22/16 9:22PM
703: Large Cardinals and Continuations/16 8/26/16 12:03AM
704: Large Cardinals and Continuations/17 8/31/16 12:55AM
705: Large Cardinals and Continuations/18 8/31/16 11:47PM
706: Second Incompleteness/1 7/5/16 2:03AM
707: Second Incompleteness/2 9/8/16 3:37PM
708: Second Incompleteness/3 9/11/16 10:33PM
709: Large Cardinals and Continuations/19 9/13/16 4:17AM
710: Large Cardinals and Continuations/20 9/14/16 1:27AM
700: Large Cardinals and Continuations/14 8/1/16 11:01AM
701: Extending Functions/1 8/10/16 10:02AM
702: Large Cardinals and Continuations/15 8/22/16 9:22PM
703: Large Cardinals and Continuations/16 8/26/16 12:03AM
704: Large Cardinals and Continuations/17 8/31/16 12:55AM
705: Large Cardinals and Continuations/18 8/31/16 11:47PM
706: Second Incompleteness/1 7/5/16 2:03AM
707: Second Incompleteness/2 9/8/16 3:37PM
708: Second Incompleteness/3 9/11/16 10:33PM
709: Large Cardinals and Continuations/19 9/13/16 4:17AM
710: Large Cardinals and Continuations/20 9/14/16 1:27AM
711: Large Cardinals and Continuations/21 9/18/16 10:42AM
712: PA Incompleteness/1 9/23/16 1:20AM
713: Foundations of Geometry/1 9/24/16 2:09PM
714: Foundations of Geometry/2 9/25/16 10:26PM
715: Foundations of Geometry/3 9/27/16 1:08AM
716: Foundations of Geometry/4 9/27/16 10:25PM
717: Foundations of Geometry/5 9/30/16 12:16AM
718: Foundations of Geometry/6 101/16 12:19PM
719: Large Cardinals and Emulations/22
720: Foundations of Geometry/7 10/2/16 1:59PM
721: Large Cardinals and Emulations//23 10/4/16 2:35AM
722: Large Cardinals and Emulations/24 10/616 1:59AM
723: Philosophical Geometry/8 10/816 1:47AM
724: Philosophical Geometry/9 10/10/16 9:36AM
725: Philosophical Geometry/10 10/14/16 10:16PM
726: Philosophical Geometry/11 Oct 17 16:04:26 EDT 2016
727: Large Cardinals and Emulations/25 10/20/16 1:37PM
728: Philosophical Geometry/12 10/24/16 3:35PM
729: Consistency of Mathematics/1 10/25/16 1:25PM
730: Consistency of Mathematics/2 11/17/16 9:50PM
731: Large Cardinals and Emulations/26 11/21/16 5:40PM
732: Large Cardinals and Emulations/27 11/28/16 1:31AM
733: Large Cardinals and Emulations/28 12/6/16 1AM
734: Large Cardinals and Emulations/29 12/8/16 2:53PM
735: Philosophical Geometry/13 12/19/16 4:24PM
736: Philosophical Geometry/14 12/20/16 12:43PM
737: Philosophical Geometry/15 12/22/16 3:24PM
738: Philosophical Geometry/16 12/27/16 6:54PM
739: Philosophical Geometry/17 1/2/17 11:50PM
740: Philosophy of Incompleteness/2 1/7/16 8:33AM
741: Philosophy of Incompleteness/3 1/7/16 1:18PM
742: Philosophy of Incompleteness/4 1/8/16 3:45AM
743: Philosophy of Incompleteness/5 1/9/16 2:32PM
744: Philosophy of Incompleteness/6 1/10/16 1/10/16 12:15AM
745: Philosophy of Incompleteness/7 1/11/16 12:40AM
746: Philosophy of Incompleteness/8 1/12/17 3:54PM
747: PA Incompleteness/2 2/3/17 12:07PM
748: Large Cardinals and Emulations/30 2/15/17 2:19AM
749: Large Cardinals and Emulations/31 2/15/17 2:19AM
750: Large Cardinals and Emulations/32 2/15/17 2:20AM
751: Large Cardinals and Emulations/33 2/17/17 12:52AM
752: Emulation Theory for Pure Math/1 3/14/17 12:57AM
753: Emulation Theory for Math Logic 3/10/17 2:17AM
754: Large Cardinals and Emulations/34 3/12/17 12:34AM
755: Large Cardinals and Emulations/35 3/12/17 12:33AM
756: Large Cardinals and Emulations/36 3/24/17 8:03AM
757: Large Cardinals and Emulations/37 3/27/17 2:39AM
758: Large Cardinals and Emulations/38 4/10/17 1:11AM
759: Large Cardinals and Emulations/39 4/10/17 1:11AM
760: Large Cardinals and Emulations/40 4/13/17 11:53PM
761: Large Cardinals and Emulations/41 4/15/17 4:54PM
762: Baby Emulation Theory/Expositional 4/17/17 1:23AM
763: Large Cardinals and Emulations/42 5/817 2:18AM
764: Large Cardinals and Emulations/43 5/11/17 12:26AM
765: Large Cardinals and Emulations/44 5/14/17 6:03PM
766: Large Cardinals and Emulations/45 7/2/17 1:22PM
767: Impossible Counting 1 9/2/17 8:28AM
768: Theory Completions 9/4/17 9:13PM
769: Complexity of Integers 1 9/7/17 12:30AM
770: Algorithmic Unsolvability 1 10/13/17 1:55PM
771: Algorithmic Unsolvability 2 10/18/17 10/15/17 10:14PM
Harvey Friedman
More information about the FOM
mailing list