New Primitive Programming Language - Is it Turing Complete?
in [Logic]
|
Prev: Cardinality, Number, and Identity
Next: Natural numbers
From: Jan Burse on 22 Dec 2009 15:47 Jan Burse schrieb: > Charlie-Boo schrieb: >> 1. Loop: FOR(X){ . . . } >> 2. Assignment: A<=B >> 3. Conditional: (A=B){ . . . } >> 4. End loop: STOP >> 5. End program: HALT A > > If 3. does not allow recursion, than it is not > turing complete (=partial recursive). Then its > only primitive recursive. Its primitive recursive, provided you are not allowed to modify the for variable, inside a for loop. It will just loop X times. Otherwise its turing complete (=partial recursive).
From: David Libert on 23 Dec 2009 01:16 Jan Burse (janburse(a)fastmail.fm) writes: > Charlie-Boo schrieb: >> 1. Loop: FOR(X){ . . . } >> 2. Assignment: A<=B >> 3. Conditional: (A=B){ . . . } >> 4. End loop: STOP >> 5. End program: HALT A > > If 3. does not allow recursion, than it is not > turing complete (=partial recursive). Then its > only primitive recursive. Early in the thread, 2nd aricle, Charlie asked about defining 0 and 1 wuthout using them as contants. If we leve off constants 0 and 1 from the language, 0 can be recovered. We can write a program for the constantly 0 function, and can write programs to assign 0 to a variable. With neither 0 or 1 constants available 1 cannot be recovered. There is no program for the constantly 1 function. So with no contants 0 or 1, the language is not Turing complete. But Charlie's original specification, from the base article of this thread, allowed constants 0 and 1 to be assigned to variables. With that basic version, the language is Turing complete for partial recursive functions over non-negative integers. -- David Libert ah170(a)FreeNet.Carleton.CA
From: H. J. Sander Bruggink on 23 Dec 2009 08:37 On 12/22/2009 06:12 AM, Charlie-Boo 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> >>>> 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?) It thought it too obvious to spell out, but here goes: a Turing Machine, by definition, has only inputs which are finite. Therefore, the domain of the function it computes is always countable. There exist uncountable sets. QED. [snip] > I have always felt that was why AOC has been controversial. The > natural formalization involves operations that cannot be performed on > sets in general. And what, in your opinion, is this "natural formalization" and what operations does it involve? [snip] > What non-r.e. set has a choice function? The set of Turing Machines > that don�t halt isnot r.e., but it has a choice function: the > smallest element in the set. The set of TMs that don't halt is not a set of non-empty sets. Do you actually know what a choice function is? [snip] groente -- Sander
From: Charlie-Boo on 20 Jan 2010 19:52 On Dec 22 2009, 11:11 am, "Jesse F. Hughes" <je...(a)phiwumbda.org> wrote: > Charlie-Boo <shymath...(a)gmail.com> writes: > > On Dec 22, 7:52 am, "Jesse F. Hughes" <je...(a)phiwumbda.org> wrote: > >> Charlie-Boo <shymath...(a)gmail.com> writes: > >> > 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.) > > >> Sure, it was a test. > > >> It looked like a stupid blunder, but it was a test. > > > Actually, I realized it after I read it one more time after posting > > it. (This happens from time to time. No need to rationalize.) I > > guess you can say it was a blunder that turned into an unintentional > > test - I did in fact wonder who would notice, of course, as would > > anyone - mayhaps even yourself? > > Sorry for the insinuation. > > But, no, I didn't wonder who would notice. I don't know who reads > your posts and with what attention. Personally, I skimmed it and > didn't bother to respond to the post generally, pointing out this one > obvious oddity and skipping over the reasonableness of Occam's razor > when it comes to mathematical theories and so on. > > > Anywho, as far as my questions about addition and multiplication, and > > the original (broader) question about characterizing what Peano's > > Axioms really say about a system that contains them go, . . . ? > > >> You're a clever one, you are. > > > As are you - when you're talking about Mathematics, i.e. > > It's nice you're trying out Latin abbreviations, but I'm not sure > you've quite got them down. How's that? (You've never been right.) C-B > > -- > Jesse F. Hughes > "You may not realize it but THOUSANDS of people read my posts. > You are putting your stupidity on wide display." > -- James S. Harris knows about wide displays of stupidity.- Hide quoted text - > > - Show quoted text -
From: Charlie-Boo on 20 Jan 2010 19:54
On Dec 22 2009, 1:17 pm, spudnik <Space...(a)hotmail.com> wrote: > I have never learned what i.e. & e.g. abbreviate, but if > they mean "that is" and "for example," then > the usual usages seem somewhat contrary to normal English grammar, > unless one uses a comma e.g.. > > --l'Oeuvre!www.wlym.com And what is wrong with "As are you - when you're talking about Mathematics, that is."? Can you ask the same question about the sentence asking the question? (In CBL you can do so in any system of mathematics.) C-B |