On Tue, Dec 18, 2018 at 8:02 AM Bruno Marchal <marc...@ulb.ac.be> wrote:
> > On 18 Dec 2018, at 06:01, Jason Resch <jasonre...@gmail.com> wrote: > > > > On Mon, Dec 17, 2018 at 10:46 PM Bruce Kellett <bhkellet...@gmail.com> > wrote: > >> On Tue, Dec 18, 2018 at 3:32 PM Jason Resch <jasonre...@gmail.com> 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. > <everything-list+unsubscr...@googlegroups.com> 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 everything-list+unsubscr...@googlegroups.com. To post to this group, send email to everything-list@googlegroups.com. Visit this group at https://groups.google.com/group/everything-list. For more options, visit https://groups.google.com/d/optout.
