Prev: Why G. Chaitin mesure of complexity is wrong.
Next: ISO old-fashioned math exercises for kids
From: Charlie-Boo on 29 Nov 2009 09:15

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.

Which of the following functions are programmable?

1. Zero
2. Less Than
3. Less than or equal.
4. Minimum of two numbers.
5. Successor
6. Addition
7. Multiplication
8 Exponentiation

Syntax:

1. Loop: FOR(X){ . . . }
2. Assignment: A<=B
3. Conditional: (A=B){ . . . }
4. End loop: STOP
5. End program: HALT A

For starters: We can check for less than by seeing which of I and J
are reached first in a loop. Variables A, B, C etc. can represent the
current state of information by being assigned values 0 and 1, and
checked if they are later equal to 0 or 1.

C-B
From: Charlie-Boo on 29 Nov 2009 09:19
On Nov 29, 9:15 am, Charlie-Boo <shymath...(a)gmail.com> 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.
>
> Which of the following functions are programmable?
>
> 1. Zero

That is, write programs for 0 and 1 without using them as constants,
so that they need not be supplied as literals in the language.

> 2. Less Than
> 3. Less than or equal.
> 4. Minimum of two numbers.
> 5. Successor
> 6. Addition
> 7. Multiplication
> 8 Exponentiation
>
> Syntax:
>
> 1. Loop: FOR(X){ . . . }
> 2. Assignment: A<=B
> 3. Conditional: (A=B){ . . . }
> 4. End loop: STOP
> 5. End program: HALT A
>
> For starters:  We can check for less than by seeing which of I and J
> are reached first in a loop.  Variables A, B, C etc. can represent the
> current state of information by being assigned values 0 and 1, and
> checked if they are later equal to 0 or 1.
>
> C-B

From: sfuerst on 29 Nov 2009 17:21
On Nov 29, 6:19 am, Charlie-Boo <shymath...(a)gmail.com> wrote:
> On Nov 29, 9:15 am, Charlie-Boo <shymath...(a)gmail.com> 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.
>
> > Which of the following functions are programmable?
>
> > 1. Zero
>
> That is, write programs for 0 and 1 without using them as constants,
> so that they need not be supplied as literals in the language.
>
> > 2. Less Than
> > 3. Less than or equal.
> > 4. Minimum of two numbers.
> > 5. Successor
> > 6. Addition
> > 7. Multiplication
> > 8 Exponentiation
>
> > Syntax:
>
> > 1. Loop: FOR(X){ . . . }
> > 2. Assignment: A<=B
> > 3. Conditional: (A=B){ . . . }
> > 4. End loop: STOP
> > 5. End program: HALT A
>
> > For starters:  We can check for less than by seeing which of I and J
> > are reached first in a loop.  Variables A, B, C etc. can represent the
> > current state of information by being assigned values 0 and 1, and
> > checked if they are later equal to 0 or 1.
>
> > C-B

Using R for "result", something like this might work. Of course, I
needed a hack for the set-to-one function.


Set to zero:
FOR(Z)
{
R <= Z
STOP
}

Set to one:
(T starts as any non-zero value)
FOR(Z)
{
(T=0)
{
R <= Z
T <= Z
STOP
}

T <= 0
}

X < Y:
FOR(Z)
{
(Z=Y)
{
R <= 0
STOP
}

(Z=X)
{
R <= 1
STOP
}
}

X <= Y:
FOR(Z)
{
(Z=X)
{
R <= 1
STOP
}

(Z=Y)
{
R <= 0
STOP
}
}

minimum:
FOR(Z)
{
(Z=X)
{
R <= X
STOP
}

(Z=Y)
{
R <= Y
STOP
}
}

successor:
F<=0
FOR(Z)
{
(F=1)
{
R <= Z
STOP
}

(Z=X)
{
F <= 1
}
}

Addition X + Y:
R <= X
FOR(Z)
{
(Y=Z)
{
STOP
}

R <= successor(R)
}

Multiplication X * Y:
R <= 0
FOR(Z)
{
(Z=Y)
{
STOP
}

R <= add(R, X)
}

Exponentiation X ** Y:
R <= 1
FOR(Z)
{
(Z=Y)
{
STOP
}

R <= multiply(R, X)
}

Steven
From: rossum on 29 Nov 2009 18:08
On Sun, 29 Nov 2009 06:15:12 -0800 (PST), Charlie-Boo
<shymathguy(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.

rossum

From: H. J. Sander Bruggink on 30 Nov 2009 05:54
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)?

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).

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

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, 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).

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

groente
-- Sander
 |  Next  |  Last
Pages: 1 2 3 4 5 6
Prev: Why G. Chaitin mesure of complexity is wrong.
Next: ISO old-fashioned math exercises for kids