New Primitive Programming Language - Is it Turing Complete?
in [Math]
|
From: Charlie-Boo on 2 Dec 2009 10:12 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 2 Dec 2009 11:08 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). Im 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 Godels 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 2 Dec 2009 12:21 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 2 Dec 2009 16:13 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: > > Im 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 4 Dec 2009 10:01
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 |