On 01/06/2012 11:48 AM, Invisible wrote:
> Theorem: The language implemented by Logic Box is Turing-complete.
>
> Proof: I have written a program in Logic Box which executes any program
> written in the SKI calculus. The SKI calculus is known to be
> Turing-complete.
>
> Actually, things are not quite so simple. But here goes...

> Unfortunately, because the OR operator tries /all/ possibilities rather
> than just keeping the first successful one, what this does is to produce
> a result set containing all possible reductions, using all possible
> reduction orders.
>
> So in summary, we can say that running the program produces a result set
> which contains the correct answer /somewhere/, plus a whole heap of
> various intermediate results. As best as I can tell, there's no way to
> determine /where/ in the solutions it is. So I'm not completely sure
> this counts as a valid proof.

Actually, it turns out that by swapping the order of some predicates, 
you can make it so that Normal Order Reduction is always solution #1. 
This conclusively proves the Turing-completeness of my little 
programming language.

It also conclusively proves something that will surprise nobody: My 
talents are wasted here.

Post a reply to this message