From: Charlie-Boo on
On Nov 29, 6:08 pm, rossum <rossu...(a)coldmail.com> wrote:
> On Sun, 29 Nov 2009 06:15:12 -0800 (PST), Charlie-Boo
>
> <shymath...(a)gmail.com> wrote:
> >Consider the following particularly simple programming language called
> >LOOP+EQ:
>
> It is known that brainfuck is Turing Complete
> (http://en.wikipedia.org/wiki/Brainfuck).  
>
> If you can write a brainfuck interpreter in LOOP+EQ then that is also
> Turing Complete.

Great idea and choice of programming languages. It is a lot different
from my LOOP+EQ language. I think we could use a general model that
includes both of these languages. I learned that when I wrote a
translator between two versions of a programming language. After
messing with direct translation, I developed a general representation
of both - translating to and from that was much simpler.

What would be the shortest programs for the 8 functions listed?

How does BF compare to LOOP+EQ - in terms of number of primitives,
size of these programs, ease of use and universality?

Notice that LOOP+EQ is universal in the sense that no particular
mathematical objects are needed. You can list many sets (or go on
forever listing only a subset) and equality is a pretty universal
relation. BF seems to have more primitives and require numbers.

C-B

> rossum

From: Charlie-Boo on
On Nov 30, 5:54 am, "H. J. Sander Bruggink" <brugg...(a)uni-due.de>
wrote:
> On 11/29/2009 03:15 PM, Charlie-Boo wrote:
>
>
>
> > Consider the following particularly simple programming language called
> > LOOP+EQ:
>
> > 1. Loop through the numbers 0, 1, 2, . . . with loop variable X or Y
> > or Z . . .
> > 2. Assign variables A, B, C . . . to a variable, constant 0 or 1, or a
> > programmable function on variables.
> > 3. Execute a (sub)program iff two given variables are equal.
> > 4. STOP loop and continue the program after the loop.
> > 5. Return variable value and stop entire program.
>
> > Inputs are variables I, J, K . . .  0 means FALSE and 1 means TRUE.
>
> What do you mean by "programmable function" (in item 2)?

A program can be written in LOOP+EQ that calculates the function, as
illustrated by the earlier programs by Steven (SFUERST) written in LOOP
+EQ.

> If you mean "programmable in LOOP+EQ", then the language is trivially
> not Turing-complete, because you cannot change the values in the
> program (the set V of values of variables and constants will never
> become bigger).

I’m not sure what you mean. Certainly variable X assumes new values
as we go through a LOOP. Can you give me an example of a programming
language making the set of values and constants bigger that cannot be
done in LOOP+EQ (as far as you can see, of course)?

> If you mean "programmable in some Turing complete language" then
> your LOOP+EQ is trivially Turing-complete (only item 2 would suffice).

Of course not. I mean programmable in LOOP+EQ. It is just to make
sure that the set of programmable functions is closed under
composition – though I would be happy to see a demonstration that it
is not necessary - there is a program for f(g) whenever there is a
program for f and g without using function calls.

> If you take some finite set of basic programmable functions (which
> includes incrementing a variable, A=A+1), then I am inclined to
> say that it is Turing-complete,

Do you not agree that LOOP+EQ does that (allows one to add one to a
given value, i.e. includes the successor function)? I would say that
it is better to leave out successor as a primitive if you can, to make
the language smaller (the whole objective) and also to make the
language more universal - no reference to numbers.

For example, can you write a LOOP+EQ program for the choice function
in the Axiom of Choice? What if the given set is empty - can we be
more precise than the axiom itself and say what the program does if
the set is empty? And would this program give us more insight into
AOC with a solid example of how it would work?

> although then it still depends on
> what exactly you mean by item 3 (in particular, whether or not it
> is allowed to recursively call a subprogram from itself).

No, the syntax is meant to illustrate that I am talking about code in
a program that is executed when reached iff two given variables are
equal.

> All in all, the semantics of your language is just not well enough
> defined to be able to say anything about its Turing-completeness.

I guess it's all a waste of time.

But then again, you did say that if it includes incrementing a
variable then you would tend to believe that it is Turing Complete.
So there the issue was not whether it is well-defined, but whether or
not it included successor. And do you agree that it does include the
successor function – the successor function is programmable in LOOP
+EQ? (See Steven's post.)

Have I answered all of your questions now? LOOP+EQ can be used to
program various functions, as shown by Steven. The question is
whether this includes all of the recursive functions. One could
follow Godel’s path in 1931 to show it includes the primitive
recursive functions (by programming the 45 functions that he does.)
(As I recall, actually number 45 was the non-r.e. relation of
unprovability.) Better yet, describe a translator from MF into LOOP
+EQ.

C-B

> groente
> -- Sander

From: H. J. Sander Bruggink on
On 12/02/2009 05:08 PM, Charlie-Boo wrote:
> On Nov 30, 5:54 am, "H. J. Sander Bruggink"<brugg...(a)uni-due.de>
> wrote:

> I�m not sure what you mean. Certainly variable X assumes new values
> as we go through a LOOP.

Ah, I see. I misunderstood your LOOP construct; I thought it was a FOR
loop, which just repeats a subprogram a fixed number of times. So yes,
your language is Turing complete.

[snip]

> Do you not agree that LOOP+EQ does that (allows one to add one to a
> given value, i.e. includes the successor function)? I would say that
> it is better to leave out successor as a primitive if you can, to make
> the language smaller (the whole objective) and also to make the
> language more universal - no reference to numbers.

There is a reference to numbers in your LOOP construct already.

>
> For example, can you write a LOOP+EQ program for the choice function
> in the Axiom of Choice?

No. First, because there is no "the" choice function. Second, because
the axiom of choice also applies to structures which are far larger than
any language which is just Turing-complete can ever hope to cope with.

groente
-- Sander
From: Charlie-Boo on
On Dec 2, 12:21 pm, "H. J. Sander Bruggink" <brugg...(a)uni-due.de>
wrote:
> On 12/02/2009 05:08 PM, Charlie-Boo wrote:
>
> > On Nov 30, 5:54 am, "H. J. Sander Bruggink"<brugg...(a)uni-due.de>
> > wrote:
> > I’m not sure what you mean.  Certainly variable X assumes new values
> > as we go through a LOOP.
>
> Ah, I see. I misunderstood your LOOP construct; I thought it was a FOR
> loop, which just repeats a subprogram a fixed number of times. So yes,
> your language is Turing complete.
>
> [snip]
>
> > Do you not agree that LOOP+EQ does that (allows one to add one to a
> > given value, i.e. includes the successor function)?  I would say that
> > it is better to leave out successor as a primitive if you can, to make
> > the language smaller (the whole objective) and also to make the
> > language more universal - no reference to numbers.
>
> There is a reference to numbers in your LOOP construct already.

The set that it loops through need not be a set of numbers. The
values that it checks for being equal need not be numbers. Looping
through a set and checking for equality apply to any domain of
discourse, certainly more than just numbers.

> > For example, can you write a LOOP+EQ program for the choice function
> > in the Axiom of Choice?
>
> No. First, because there is no "the" choice function.

How about "a choice function"?

> Second, because
> the axiom of choice also applies to structures which are far larger than
> any language which is just Turing-complete can ever hope to cope with.

Can you formally define any of that?

A<=0
FOR(X){ B<=X A<=1 STOP }
(A=0){ HALT "Set is empty" }
HALT B

See?

C-B

> groente
> -- Sander

From: H. J. Sander Bruggink on
On 12/02/2009 10:13 PM, Charlie-Boo wrote:
> On Dec 2, 12:21 pm, "H. J. Sander Bruggink"<brugg...(a)uni-due.de>
> wrote:
>> On 12/02/2009 05:08 PM, Charlie-Boo wrote:

>>> Do you not agree that LOOP+EQ does that (allows one to add one to a
>>> given value, i.e. includes the successor function)? I would say that
>>> it is better to leave out successor as a primitive if you can, to make
>>> the language smaller (the whole objective) and also to make the
>>> language more universal - no reference to numbers.
>>
>> There is a reference to numbers in your LOOP construct already.
>
> The set that it loops through need not be a set of numbers. The
> values that it checks for being equal need not be numbers. Looping
> through a set and checking for equality apply to any domain of
> discourse, certainly more than just numbers.

False. Your loop construct requires the domain of discourse to have
a start object and a "successor" function. So the domain of discourse
needs to be recursively enumerable.

>
>>> For example, can you write a LOOP+EQ program for the choice function
>>> in the Axiom of Choice?
>>
>> No. First, because there is no "the" choice function.
>
> How about "a choice function"?
>
>> Second, because
>> the axiom of choice also applies to structures which are far larger than
>> any language which is just Turing-complete can ever hope to cope with.
>
> Can you formally define any of that?

Sure. Google for cardinal numbers.

>
> A<=0
> FOR(X){ B<=X A<=1 STOP }
> (A=0){ HALT "Set is empty" }
> HALT B
>
> See?

I guess this program is supposed to be a choice function. Since your
programming language only works for recursively enumerable sets (see
above), it is hardly surprising that you can write a choice function
(for those sets) in it.

groente
-- Sander
First  |  Prev  |  Next  |  Last
Pages: 1 2 3 4 5 6
Prev: Cardinality, Number, and Identity
Next: Natural numbers