[FOM] 770: Algorithmic Unsolvability 1
Harvey Friedman
hmflogic at gmail.com
Fri Oct 13 13:55:12 EDT 2017
New paper link:
https://u.osu.edu/friedman.8/foundational-adventures/downloadable-manuscripts/
95. Integer Inner Product and Algorithmic Unsolvability, 23 pages,
October 13, 2017.
CONTEXT:
The two most well known and profound long term themes (in terms of
general intellectual interest and age) in the foundations of
mathematics are INCOMPLETENESS and ALGORITHMIC UNSOLVABILITY.
Both went through their profound initial developments in the 1930's.
By 1970, both had reached a substantially higher level of development
culminating in MRDP, 1970, and Solovay measure/category in 1970.
However, even by 1970, taken as a whole, the progress in
INCOMPLETENESS had a significantly greater *general intellectual
interest* than progress in ALGORITHMIC UNSOLVABILITY in terms of the
wider intellectual community.
Since then, the gap in progress has widened in that since the 1970's,
INCOMPLETENESS has gone far beyond the 1970 situation in radical ways,
particularly through CONCRETE MATHEMATICAL INCOMPLETENESS.
The question is: what kind of radical breakthrough can we look forward
to in ALGORITHMIC UNSOLVABILITY? That is a major focus of what I want
to talk about in this series on ALGORITHMIC UNSOLVABILITY.
While I was in school, 1964-1967, Cohen's breakthrough had sunk in,
and there was ALREADY widespread discussion and even anticipation of
the further radical breakthrough of CONCrETE MATHEMATICAL
INCOMPLETENESS, and considerable parts, but by no means all, of the
anticipated breakthroughs were and are continuing to be realized over
an extended period of time.
We don't have a really analogous situation with ALGORITHMIC UNSOLVABILITY.
CAVEAT: I have worked far far more on INCOMPLETENESS than ALGORITHMIC
UNSOLVABILITY,, and so there are probably substantial developments I
should be aware of in the latter, but I am not. I like, e.g.,
B. Poonen, Undecidable Problems: A Sampler, https://arxiv.org/pdf/1204.0299.pdf
U. Andrews, Undecidable Problems in Topology,
https://math.berkeley.edu/~hutching/teach/215b-2005/andrews.ps
>From U. Andrews:
"So, it seems that the strength of undecidability results in geometry
and topology relies largely or entirely on the connections to algebra.
Indeed, it is directly through the algebraic topological invariants
that we have been able to prove undecidability of some topological
problems."
I plan to discuss the situation with regard to ALGORITHMIC
UNSOLVABILITY in much greater depth, particularly with regard to the
question of what shape a radical level breakthrough could or maybe
will look like. With regard to INCOMPLETENESS, the corresponding
question was more or less clear for decades, namely, what amounts to
CONCRETE MATHEMATICAL INCOMPLETENESS, which is well under way. Of
course, further revelation level breakthroughs going forward in
CONCRETE MATHEMATICAL INCOMPLETENESS are required to realize the great
promise of INCOMPLETENESS and f.o.m. generally.
In 2010, I did find an essentially new systematic arena for
ALGORITHMIC UNSOLVABILITY with
https://u.osu.edu/friedman.8/foundational-adventures/downloadable-manuscripts/
64. Decision Problems in Euclidean Geometry. August 29, 2010, 33 pages.
The above is rather systematic. We are given a finite diagram of a
familiar kind in the setting of Euclidean geometry, and we ask whether
the diagram can be realized in the usual Euclidean plane with integer
points. For a number of very familiar kinds of Euclidean type
diagrams, this problem is ALGORITHMICALLY UNSOLVABLE. The paper is
fairly well polished, but if I recall, I was intending to polish it
some more.
In this context of Euclidean type diagrams, asking for integer points
is quite natural, but I think it can be made yet more natural by
adjusting the setup somewhat. One way to do this is to require that
two distinct points be designated, as part of the diagram, for the
"unit of measurement". Then we can insist that some specified pairs of
points are required to have distance a multiple of the unit of
measurement. There are some interesting variants of this idea that
need to be considered as well, so I am anticipating a complex of
ALGORITHMIC UNSOLVABILITY results along these lines.
I have just put a paper up on my website which focuses on INNER PRODUCTS.
https://u.osu.edu/friedman.8/foundational-adventures/downloadable-manuscripts/
95. Integer Inner Product and Algorithmic Unsolvability, 23 pages,
October 13, 2017.
I do NOT consider my #64 and #95 to be even close to the kind of
revolutionary breakthrough in ALGORITHMIC UNSOLVABILITY that we are
looking for, however. The question is: what should we be looking for?
There is still the idea of not venturing too far out, and simply
looking forward to the obvious possible breakthroughs in Hilbert's
10th Problem, of which there are many stunning possibilities. However,
progress on this has been notoriously stubborn but not entirely
absent. At the moment, and for quite some time, radical breakthroughs
in and around Hilbert's Tenth Problem, at the level of general
intellectual interest that we are talking about, look intractable. But
I don't think they are intractable over very seriously long time
frames like 100 years.
Here is the cover page of #95:
INTEGER INNER PRODUCTS AND ALGORITHMIC UNSOLVABILITY
by
Harvey M. Friedman
Distinguished University Professor of Mathematics, Philosophy, and
Computer Science Emeritus
Ohio State University
Columbus, Ohio
October 13, 2017
Abstract. Is there a finite list of integer triples with a given
partial list of integer inner products? Is there a finite list of
integers with a given partial list of integer inner products between
various pairs? We prove that these problems are algorithmically
unsolvable by reduction from Hilbert's 10th Problem (over the
integers). The status of the first problem for pairs is unresolved.
1. Introduction.
2. Partial Inner Product Specification.
3. Number Based Inner Product Specification.
4. Additional Variants and Open Questions.
************************************************************************
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 770th 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
Harvey Friedman
More information about the FOM
mailing list