On Tue, Dec 18, 2018 at 8:02 AM Bruno Marchal <[email protected]> wrote:
> > On 18 Dec 2018, at 06:01, Jason Resch <[email protected]> wrote: > > > > On Mon, Dec 17, 2018 at 10:46 PM Bruce Kellett <[email protected]> > wrote: > >> On Tue, Dec 18, 2018 at 3:32 PM Jason Resch <[email protected]> wrote: >> >>> >>> I have no idea what you mean by "an incorrect computation". >>> >> >> Have you never made an arithmetical error? >> >> > This posits some expectation of a particular result. But in the set of all > computations, all computations exist. What is an incorrect computation? > Incorrect with respect to what? So long as the computation is the result > of a functioning Turing machine nothing it does can be called an "incorrect > computation". > > (Note the context is we're talking about arithmetical computations, not > physical machines that can be faulty, or ill-designed, or crash, etc. And > the concept of a buggy program or a program that loops infinitely is only a > relevant when some person expects some different behavior out of the > program. In the set of call computations, there is no concept of an > incorrect vs. a correct computation, there are just computations.) > > > > That is well illustrated by Ehud Shapiro’s debugging algorithm(*) in > PROLOG. > > It works well on simple programs. You let it compute, and when he gives a > “wrong answer”, you just tell him, or tell it. Eventually (on simple > sequences of corrections) it debugs the program. > > Now, if you give the empty program, you can do the same and debug it, from > any sequence of input-output you have in mind, and eventually it converges > on the program you were thinking about. He synthesised the usual factorial > function from the debugging of the empty program. > > This illustrates well that a “bug” is a goal oriented notion. > > In some sense, the universal dovetailer emulates all programs, with all > possible bugs, (including the grammatical error (if we want), as those can > be mechanically skipped, unlike the possible unwanted loop), which are of > course correct looping programs, if the goal was to do some loop. > > A program is correct with respect to some specification, but in the space > of all computations, the notion of correctness does not make sense. > > Bruno > > (*) Algorithmic Program Debugging, Ehud Shapiro, MIT Press, 1983. > <[email protected]> That's fascinating. Thanks for the reference. On the topic of "teaching programs", this made the news today: https://www.tomsguide.com/us/nvidia-ai-faces-generative-adversarial-network,news-28869.html Jason -- You received this message because you are subscribed to the Google Groups "Everything List" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected]. To post to this group, send email to [email protected]. Visit this group at https://groups.google.com/group/everything-list. For more options, visit https://groups.google.com/d/optout.
