[FOM] Digital Display Expansion

Harvey Friedman hmflogic at gmail.com
Sun Jul 9 03:30:09 EDT 2017

I have posted a paper on Digital Display Expansion at

93. Digital Display Expansion, July 7, 2017, 18 pages. I wanted to get
this out quickly. An advanced draft, but still needs more proofreading
and polishing. Will update soon.

I will continue to polish and proofread, but I thought it worthwhile
to get the ideas out right away.

PS: I have already decided to change the name from Digital Display

I will revise slightly the abstract below here on the FOM and wait for
a substantive revision to the paper before I change it here. Here is
the revision that reflects this change from "expansion" to

Harvey M. Friedman
July 7, 2017

Abstract. We construct a digital display with 376 x 376 pixels and 382
colors, which is fully enrichable, but where its full enrichability is
not provable from the usual ZFC axioms for mathematics (all assuming
ZFC is consistent). Here full enrichability means that the display can
be indefinitely enriched with new pixels without creating any new 2 by
2 contiguous parts (4 element cells). By comparison, the daily
production of digital displays from computer screens, smartphones,
televisions, movies, digital photographs, satellite images, digital
audio and MIDI recordings, and the like, results in perhaps trillions
of incomparably larger digital displays per day, worldwide. We achieve
this by a reinterpretation of recent work of Aaronson, Yeddida,
myself, and O'Rear on the halting problem for Turing machines, that
closely relates it to digital displays. This simple but basic
conceptual shift opens up immediately transparent profound and
challenging new dramatic areas of research at the interface of at
least mathematical logic, combinatorics, computer science, and art.
Aside from the obvious goal of finding increasingly small digital
displays so representing ZFC Incompleteness, there are other even
deeper issues. Specifically, is full enrichability expected or not, in
random displays, on various adjustments of the parameters (number of
pixels and number of colors)? What are the thresholds? Cen these
thresholds be determined in ZFC? Are there thresholds where we expect
ZFC Incompleteness to arise? And what about the rich digital displays
randomly drawn from daily life such as from typical movies and musical
recordings (digital audio and MIDI)? How invisibly can we doctor
existing digital displays so as to represent ZFC Incompleteness? Our
method of generating digital displays of various sizes exhibiting such
ZFC Incompleteness is very flexible, raising the prospect of creating
beautiful digital displays of various sizes meeting various criteria.
In fact, we envision a creative process of adjusting colors and
rearranging patterns, transforming a digital display from an unsightly
mess to a work of art of equal size. This should also be approached on
the musical side with digital and MIDI recordings, in a joint effort
of mathematical logicians, combinatorists, computer scientists, audio
engineers, and musicians.

Harvey Friedman

More information about the FOM mailing list