New Primitive Programming Language - Is it Turing Complete?
in [Logic]
|
Prev: Cardinality, Number, and Identity
Next: Natural numbers
From: Charlie-Boo on 20 Dec 2009 11:02 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. And is there a simpler Turing complete language? Notice that I have the loop as given and derive the first and next functions. Contrast that with Peano's Axioms that give you the first and next functions, from which you construct the loop (induction rule.) Since we are talking about the primitives of the language, by Occam's Razor we should minimize the number of primitives at this point. So we can define a simpler language if we have as given the fact that the language can create a loop of all values. That means that the universal set is representable. There is a wff w1(x) that is provable for all values x being substituted for the x. Peano Arithmetic is defined at the wrong level of abstraction. Any system in which the universal set is representable will do, which includes the PA model of zero and successor, but also includes simpler systems based on the loop being primitive, such as LOOP+EQ. C-B > [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: Jesse F. Hughes on 20 Dec 2009 11:45 Charlie-Boo <shymathguy(a)gmail.com> writes: > That means that the universal set is representable. There is a wff > w1(x) that is provable for all values x being substituted for the x. Right. Like, say, w1(x) could be x = x. How is this fascinating? -- Jesse F. Hughes "You do know that after the get done with [outlawing] cigarettes, they're gonna come after guns, right?" -- AM talk radio host Mike Gallagher
From: Charlie-Boo on 21 Dec 2009 23:06 On Dec 20, 11:45 am, "Jesse F. Hughes" <je...(a)phiwumbda.org> wrote: > Charlie-Boo <shymath...(a)gmail.com> writes: > > That means that the universal set is representable. There is a wff > > w1(x) that is provable for all values x being substituted for the x. > > Right. Like, say, w1(x) could be x = x. > > How is this fascinating? Yes, that's right. (I was wondering if anyone would notice.) Any axiom (and add a reference to x if you must) will do. But what is different about Peano's way of making sure that we can prove that every number is a number? That I haven't thought through. But the fact that the addition and multiplication relations are also representable (the other 2/3 of Peano's Axioms) has no trivial alternative, does it? Reducing primitives is definitely something worthwhile and possible. It's possible because true primitives cannot be complex (as complex as Peano's Axioms). This (I have always said) is not possible otherwise we can use simpler expresssions that define smaller concepts than the primitives. TRUE/PR ADD/PR MUL/PR I have discussed at least 3 or 4 approaches to reducing Peano's Axioms. For example, the simple computer program to generate the natural numbers using assignment, output and goto contains Peano's Axioms implicitly. It would be good to put them all together into a coherent treatment. C-B > -- > Jesse F. Hughes > "You do know that after the get done with [outlawing] cigarettes, > they're gonna come after guns, right?" > -- AM talk radio host Mike Gallagher
From: Charlie-Boo on 22 Dec 2009 00:12 On Dec 4, 10:01 am, "H. J. Sander Bruggink" <brugg...(a)uni-due.de> wrote: > 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. Yes. As I said, You can list many sets (or go on forever listing only a subset) but you have to list the universal set for all these programs to work (e.g. to be assured that you will reach any given number.) > >>> 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. It doesn't define "far larger" or "cope with". (Can you?) > > 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. But all of the programming languages likewise work only for r.e. universal sets and in how many of them (or any other languages, for that matter) can you write the choice function? I guess we also have the first higher order programming language. I have always felt that was why AOC has been controversial. The natural formalization involves operations that cannot be performed on sets in general. Yes! So, does that mean that only r.e. sets have choice functions? If we agreed with that then we mustve found a counter-example to AOC. What non-r.e. set has a choice function? The set of Turing Machines that dont halt is not r.e., but it has a choice function: the smallest element in the set. You see, in higher order programming languages (e.g. LOOP+EQ, or should I say i.e. LOOP+EQ) we can express the program but we cant execute it. And guess what? Functions dont need to be executed for the AOC! C-B > groente > -- Sander
From: Charlie-Boo on 22 Dec 2009 00:34
On Dec 22, 12:12 am, Charlie-Boo <shymath...(a)gmail.com> wrote: > On Dec 4, 10:01 am, "H. J. Sander Bruggink" <brugg...(a)uni-due.de> > wrote: > > > > > > > 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. > > Yes. As I said, You can list many sets (or go on forever listing > only a subset) but you have to list the universal set for all these > programs to work (e.g. to be assured that you will reach any given > number.) > > > >>> 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. > > It doesn't define "far larger" or "cope with". (Can you?) > > > > 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. > > But all of the programming languages likewise work only for r.e. > universal sets and in how many of them (or any other languages, for > that matter) can you write the choice function? > > I guess we also have the first higher order programming language. > > I have always felt that was why AOC has been controversial. The > natural formalization involves operations that cannot be performed on > sets in general. > > Yes! So, does that mean that only r.e. sets have choice functions? > If we agreed with that then we mustve found a counter-example to AOC. > > What non-r.e. set has a choice function? The set of Turing Machines > that dont halt is not r.e., but it has a choice function: the > smallest element in the set. Addendum: How do we know that this set is one for which a choice function should produce a value? The answer is proven using Godel's 1st Theorem - applied very directly. The puzzle is, how? C-B > You see, in higher order programming languages (e.g. LOOP+EQ, or > should I say i.e. LOOP+EQ) we can express the program but we cant > execute it. And guess what? Functions dont need to be executed for > the AOC! > > C-B > > > > > groente > > -- Sander- Hide quoted text - > > - Show quoted text -- Hide quoted text - > > - Show quoted text - |