Limit computable maximum (Giovanni Lagnese)

[Vasco Brattka]

The maximum max(f[0,1]) of a computable function f:[0,1] -> R is always
computable. This is a classical result in computable analysis.

It was an open problem posed by Grzegorczyk in 1955 whether the maximum
is always attained at a computable input too. This was answered in the
negative by Lacombe in 1957 and Specker in 1959.

In fact, it is easy to show that the problem of finding a point
where a given continuous function f of the above type attains its
maximum is Weihrauch equivalent to WKL (Weak König's Lemma).

(The corresponding statement is also equivalent to WKL over RCA_0 in
reverse mathematics.)

Using the Low Basis Theorem of Jockusch and Soare one can conclude
that every computable function f attains its maximum at a low input
(i.e., an input whose Turing jump is equivalent to the halting problem).
This is means that the maximum is attained at an input that is
"almost computable", which is even better than being limit computable.

In fact, by determining the Weihrauch complexity of theorems/problems
one gets a very fine classification of the corresponding uniform
computational behavior of these theorems/problems and non-uniform
questions, such as the above question, can easily be derived as
corollaries.

These and other similar examples are discussed from a historical
perspective in my article

https://arxiv.org/pdf/1602.07509.pdf

Vasco Brattka






Am 16.08.2021 um 18:00 schrieb fom-request at cs.nyu.edu:
> Send FOM mailing list submissions to
> 	fom at cs.nyu.edu
> 
> To subscribe or unsubscribe via the World Wide Web, visit
> 	https://cs.nyu.edu/mailman/listinfo/fom
> or, via email, send a message with subject or body 'help' to
> 	fom-request at cs.nyu.edu
> 
> You can reach the person managing the list at
> 	fom-owner at cs.nyu.edu
> 
> When replying, please edit your Subject line so it is more specific
> than "Re: Contents of FOM digest..."
> 
> 
> Today's Topics:
> 
>     1. Limit computable maximum (Giovanni Lagnese)
> 
> 
> ----------------------------------------------------------------------
> 
> Message: 1
> Date: Mon, 16 Aug 2021 02:10:40 +0200
> From: Giovanni Lagnese <giov.lagn at gmail.com>
> To: fom at cs.nyu.edu
> Subject: Limit computable maximum
> Message-ID:
> 	<CAFFjdjoOTkwrBSYfc4HbS7BrXwJ5iWwZEemBkE8Epxeuo2M73A at mail.gmail.com>
> Content-Type: text/plain; charset="utf-8"
> 
> Is there a computable function f : [0, 1] --> R that has no limit
> computable maximum?
> -------------- next part --------------
> An HTML attachment was scrubbed...
> URL: </pipermail/fom/attachments/20210816/e412026d/attachment-0001.html>
> 
> ------------------------------
> 
> Subject: Digest Footer
> 
> _______________________________________________
> FOM mailing list
> FOM at cs.nyu.edu
> https://cs.nyu.edu/mailman/listinfo/fom
> 
> 
> ------------------------------
> 
> End of FOM Digest, Vol 224, Issue 17
> ************************************
>