On Tuesday, December 28, 2021 at 7:11:43 AM UTC, Jeffrey Rubard wrote:
> Okay everybody,
> Time to 'enlighten' the multitude.
>
> Maybe not everyone knows that 'Turing-complete' programming languages have several other models equivalent to the Turing machine. Could you 'rate' the different formalisms?
>
> 1) Turing Machines
> 2) Lambda Calculus
> 3) Post production systems
> 4) Combinatory logic (Curry)
> 5) Kleene general recursion
> 6) Herbrand-Goedel computability
> 7) Linear logic?

I think my favourite is birds, as described in "To Mock a Mockingbird", which I think is a disguised version of option (4).

On Wednesday, October 19, 2022 at 6:10:31 PM UTC-7, Ben Bacarisse wrote:
> Hey! A topical post!
> Rock Brentwood <rockbr...@gmail.com> writes:
>
> > On Tuesday, December 28, 2021 at 1:11:43 AM UTC-6, Jeffrey Rubard wrote:
> >> Maybe not everyone knows that 'Turing-complete' programming languages have several other models equivalent to the Turing machine. Could you 'rate' the different formalisms?
> >> 1) Turing Machines
> >> 2) Lambda Calculus
> >
> > Lambda Calculus with infinitary terms (and the conditional operator).
> > Notation: x = A, B means (lambda x B) A
> Curious notation. Is it your own? Presumably
>
> x=A, y=B, C
>
> means
>
> (lambda x ((lambda y C) B)) A
>
> rather than the more usual
>
> (lambda x (lambda y C)) A B
>
> I say "more usual" because this is the way a Curried function with two
> arguments would usually be written.
> > Notation: A? B: C is B is A is true and is C if A is false
> So it would seem that this is not the pure lambda calculus as true and
> false, along with the conditional form are language primitives and not
> defined expressions.
> > Example 1:
> > x = 0, y = 1, x < n? (x = x + 1, y = y*x, x < n? (x = x + 1, y = y*x, x < n? (...): y): y): y
> > where the infinitary term denoted by (...) is an exact replica of (x =
> > x + 1, y = y*x, x< n? (...): y).
> >
> > The value of this expression is n!, the factorial of n, assuming that
> > n is a non-negative integer.
> I can see you need y*x be to be evaluated in an environment that has
> already bound x to x+1 so
>
> x=A, y=B, C must be (lambda x ((lambda y C) B)) A
>
> This raises the question of how you write
>
> (lambda x (lambda y C)) A B
>
> in this notation.
> > The value is 1, if n is a negative integer.
> >
> > Notation: Use L: E as a way to denote the (possibly infinitary)
> > subexpression E by the label L
> > Notation: Use "goto L" as a way to refer to the subexpression that the
> > label L denotes
>
> > Example 2:
> > x? (y? (z? A: B): C): (z? A: B)
> > may be rewritten as
> > x? (y? goto W: C): goto W
> > W: z? A: B
> >
> > Example 3: Example 1 rewritten with labels and gotos
> > x = 0, y = 1, goto Z
> > Z: x < n? (x = x + 1, y = y*x, goto Z): y
> I think this is going to get hard to follow because the expression named
> Z is no longer nested inside the lambda forms that bind some of the
> names within it.
>
> I would find a named, nested expression easier to follow:
>
> x = 0, y = 1, BODY:[x < n? (x = x + 1, y = y*x, BODY): y]
>
> I'm not seeing the advantages of this notation.
>
> --
> Ben.

Yeah, I've heard of the lambda calculus.
"Recently?"
No, it didn't come up.

On Wednesday, October 19, 2022 at 8:10:31 PM UTC-5, Ben Bacarisse wrote:
> Hey! A topical post!
> > Lambda Calculus with infinitary terms (and the conditional operator).
> > Notation: x = A, B means (lambda x B) A
> Curious notation. Is it your own? Presumably
>
> x=A, y=B, C
>
> means
>
> (lambda x ((lambda y C) B)) A

.... which is all it can mean, since x = A, y = B, C means x = A, (y = B, C), and x = a, f (which is often written as "let x = a in f") stands for (λxf)a ... which is standard notation, in case you forgot. It's just a more natural abbreviated form of it, without the "let" or "in" as you (presumably) already know.

So x = A, (y = B, C) mean x = A, ((λyC) B) means λx((λyC)B)A.
> rather than the more usual

No. There is no "more usual".
let x = A in let y = B in C means λx((λyC)B)A.

> This raises the question of how you write
>
> (lambda x (lambda y C)) A B

the same way as you always do:
(λx(λyC))BA
or equivalently as
(x = B, λyC)A
which (in the less abbreviated form) is
(let x = B in λyC)A

Perhaps you missed the part up at the top where it said:
> Lambda Calculus *with* infinitary terms
that means *extension of* not *replacement for*.

> I'm not seeing the advantages of this notation.

An upward extension of a given language is *always* more useful or "advantageous" than the language it extends - almost by definition of "useful" ... provided the language, itself, has the same meaning (and parsing) in the extension as it does in the original ... since it includes the original language, itself, and adds more. That's universally true, regardless of the context or situation and independently of how "useful" or "advantage" is defined.

On 15/08/2023 23:57, Rock Brentwood wrote:
> An upward extension of a given language is *always* more useful or
> "advantageous" than the language it extends - almost by definition of
> "useful" ... provided the language, itself, has the same meaning (and
> parsing) in the extension as it does in the original ... since it
> includes the original language, itself, and adds more. That's
> universally true, regardless of the context or situation and
> independently of how "useful" or "advantage" is defined.

Not so. Certainly an upwards extension has extra uses and/or
advantages; but it comes with extra costs and disadvantages, so is
not necessarily overall more useful or advantageous. The extended
language is typically harder to learn, to write documentation for,
to compile, to debug, to maintain, .... All too often, what started
as a simple one-person project that was Really Useful turns into a
huge monolith that only a major company can handle.

The trouble is, perhaps, that "just one more" feature always
seems better, but over a period that too often grows into a hundred
new features, each of which someone somewhere finds useful but the
vast majority of which are useless to the vast majority of users.
There are examples of such bloatware all over computing, mathematics
and the Real World.

--
Andy Walker, Nottingham.
Andy's music pages: www.cuboid.me.uk/andy/Music
Composer of the day: www.cuboid.me.uk/andy/Music/Composers/Sinding

On 10/19/2022 5:46 PM, Rock Brentwood wrote:
> On Tuesday, December 28, 2021 at 1:11:43 AM UTC-6, Jeffrey Rubard wrote:
>> Maybe not everyone knows that 'Turing-complete' programming languages have several other models equivalent to the Turing machine. Could you 'rate' the different formalisms?
>> 1) Turing Machines
>> 2) Lambda Calculus
>
> Lambda Calculus with infinitary terms (and the conditional operator).
> Notation: x = A, B means (lambda x B) A
> Notation: A? B: C is B is A is true and is C if A is false
> Example 1:
> x = 0, y = 1, x < n? (x = x + 1, y = y*x, x < n? (x = x + 1, y = y*x, x < n? (...): y): y): y
> where the infinitary term denoted by (...) is an exact replica of (x = x + 1, y = y*x, x< n? (...): y).
>
> The value of this expression is n!, the factorial of n, assuming that n is a non-negative integer.
> The value is 1, if n is a negative integer.
>
> Notation: Use L: E as a way to denote the (possibly infinitary) subexpression E by the label L
> Notation: Use "goto L" as a way to refer to the subexpression that the label L denotes
> Example 2:
> x? (y? (z? A: B): C): (z? A: B)
> may be rewritten as
> x? (y? goto W: C): goto W
> W: z? A: B
>
> Example 3: Example 1 rewritten with labels and gotos
> x = 0, y = 1, goto Z
> Z: x < n? (x = x + 1, y = y*x, goto Z): y

For my purposes the best formalism would be a variation of a RASP
machine because this could form a bridge between Turing machines and
high level languages.

The problem with low level languages such as the Turing Machine
description languages is that they make understanding the underlying
algorithm specified in this language infeasibly difficult for any
complex algorithms.

When we understand that relative addressing can provided access to
unlimited memory then the x64 RIP addressing mode defines an abstract
machine with unlimited memory.

We don't even need this for all algorithms that don't need more memory
than the amount of memory that is available.

--
Copyright 2023 Olcott "Talent hits a target no one else can hit; Genius
hits a target no one else can see." Arthur Schopenhauer

On Wednesday, August 16, 2023 at 9:42:00 AM UTC-7, olcott wrote:
> On 10/19/2022 5:46 PM, Rock Brentwood wrote:
> > On Tuesday, December 28, 2021 at 1:11:43 AM UTC-6, Jeffrey Rubard wrote:
> >> Maybe not everyone knows that 'Turing-complete' programming languages have several other models equivalent to the Turing machine. Could you 'rate' the different formalisms?
> >> 1) Turing Machines
> >> 2) Lambda Calculus
> >
> > Lambda Calculus with infinitary terms (and the conditional operator).
> > Notation: x = A, B means (lambda x B) A
> > Notation: A? B: C is B is A is true and is C if A is false
> > Example 1:
> > x = 0, y = 1, x < n? (x = x + 1, y = y*x, x < n? (x = x + 1, y = y*x, x < n? (...): y): y): y
> > where the infinitary term denoted by (...) is an exact replica of (x = x + 1, y = y*x, x< n? (...): y).
> >
> > The value of this expression is n!, the factorial of n, assuming that n is a non-negative integer.
> > The value is 1, if n is a negative integer.
> >
> > Notation: Use L: E as a way to denote the (possibly infinitary) subexpression E by the label L
> > Notation: Use "goto L" as a way to refer to the subexpression that the label L denotes
> > Example 2:
> > x? (y? (z? A: B): C): (z? A: B)
> > may be rewritten as
> > x? (y? goto W: C): goto W
> > W: z? A: B
> >
> > Example 3: Example 1 rewritten with labels and gotos
> > x = 0, y = 1, goto Z
> > Z: x < n? (x = x + 1, y = y*x, goto Z): y
> For my purposes the best formalism would be a variation of a RASP
> machine because this could form a bridge between Turing machines and
> high level languages.
>
> The problem with low level languages such as the Turing Machine
> description languages is that they make understanding the underlying
> algorithm specified in this language infeasibly difficult for any
> complex algorithms.

"Does it occur to you that this 'copypasta' of yours is... perhaps too stupid for the 'hoaxing' purposes you want it to serve?"

On Wednesday, August 16, 2023 at 12:16:22 PM UTC-7, Jeffrey Rubard wrote:
> On Wednesday, August 16, 2023 at 9:42:00 AM UTC-7, olcott wrote:
> > On 10/19/2022 5:46 PM, Rock Brentwood wrote:
> > > On Tuesday, December 28, 2021 at 1:11:43 AM UTC-6, Jeffrey Rubard wrote:
> > >> Maybe not everyone knows that 'Turing-complete' programming languages have several other models equivalent to the Turing machine. Could you 'rate' the different formalisms?
> > >> 1) Turing Machines
> > >> 2) Lambda Calculus
> > >
> > > Lambda Calculus with infinitary terms (and the conditional operator).
> > > Notation: x = A, B means (lambda x B) A
> > > Notation: A? B: C is B is A is true and is C if A is false
> > > Example 1:
> > > x = 0, y = 1, x < n? (x = x + 1, y = y*x, x < n? (x = x + 1, y = y*x, x < n? (...): y): y): y
> > > where the infinitary term denoted by (...) is an exact replica of (x = x + 1, y = y*x, x< n? (...): y).
> > >
> > > The value of this expression is n!, the factorial of n, assuming that n is a non-negative integer.
> > > The value is 1, if n is a negative integer.
> > >
> > > Notation: Use L: E as a way to denote the (possibly infinitary) subexpression E by the label L
> > > Notation: Use "goto L" as a way to refer to the subexpression that the label L denotes
> > > Example 2:
> > > x? (y? (z? A: B): C): (z? A: B)
> > > may be rewritten as
> > > x? (y? goto W: C): goto W
> > > W: z? A: B
> > >
> > > Example 3: Example 1 rewritten with labels and gotos
> > > x = 0, y = 1, goto Z
> > > Z: x < n? (x = x + 1, y = y*x, goto Z): y
> > For my purposes the best formalism would be a variation of a RASP
> > machine because this could form a bridge between Turing machines and
> > high level languages.
> >
> > The problem with low level languages such as the Turing Machine
> > description languages is that they make understanding the underlying
> > algorithm specified in this language infeasibly difficult for any
> > complex algorithms.
> "Does it occur to you that this 'copypasta' of yours is... perhaps too stupid for the 'hoaxing' purposes you want it to serve?"

It does occur to me that your 'routines' are too stupid, often.

On Friday, August 18, 2023 at 1:13:25 PM UTC-7, Jeffrey Rubard wrote:
> On Wednesday, August 16, 2023 at 12:16:22 PM UTC-7, Jeffrey Rubard wrote:
> > On Wednesday, August 16, 2023 at 9:42:00 AM UTC-7, olcott wrote:
> > > On 10/19/2022 5:46 PM, Rock Brentwood wrote:
> > > > On Tuesday, December 28, 2021 at 1:11:43 AM UTC-6, Jeffrey Rubard wrote:
> > > >> Maybe not everyone knows that 'Turing-complete' programming languages have several other models equivalent to the Turing machine. Could you 'rate' the different formalisms?
> > > >> 1) Turing Machines
> > > >> 2) Lambda Calculus
> > > >
> > > > Lambda Calculus with infinitary terms (and the conditional operator).
> > > > Notation: x = A, B means (lambda x B) A
> > > > Notation: A? B: C is B is A is true and is C if A is false
> > > > Example 1:
> > > > x = 0, y = 1, x < n? (x = x + 1, y = y*x, x < n? (x = x + 1, y = y*x, x < n? (...): y): y): y
> > > > where the infinitary term denoted by (...) is an exact replica of (x = x + 1, y = y*x, x< n? (...): y).
> > > >
> > > > The value of this expression is n!, the factorial of n, assuming that n is a non-negative integer.
> > > > The value is 1, if n is a negative integer.
> > > >
> > > > Notation: Use L: E as a way to denote the (possibly infinitary) subexpression E by the label L
> > > > Notation: Use "goto L" as a way to refer to the subexpression that the label L denotes
> > > > Example 2:
> > > > x? (y? (z? A: B): C): (z? A: B)
> > > > may be rewritten as
> > > > x? (y? goto W: C): goto W
> > > > W: z? A: B
> > > >
> > > > Example 3: Example 1 rewritten with labels and gotos
> > > > x = 0, y = 1, goto Z
> > > > Z: x < n? (x = x + 1, y = y*x, goto Z): y
> > > For my purposes the best formalism would be a variation of a RASP
> > > machine because this could form a bridge between Turing machines and
> > > high level languages.
> > >
> > > The problem with low level languages such as the Turing Machine
> > > description languages is that they make understanding the underlying
> > > algorithm specified in this language infeasibly difficult for any
> > > complex algorithms.
> > "Does it occur to you that this 'copypasta' of yours is... perhaps too stupid for the 'hoaxing' purposes you want it to serve?"
> It does occur to me that your 'routines' are too stupid, often.

"What's a 'PLO'?"
"The Palestine Liberation Organization."
"What does Fatah have to do with computer science?"

On Monday, August 21, 2023 at 8:39:30 AM UTC-7, Jeffrey Rubard wrote:
> On Friday, August 18, 2023 at 1:13:25 PM UTC-7, Jeffrey Rubard wrote:
> > On Wednesday, August 16, 2023 at 12:16:22 PM UTC-7, Jeffrey Rubard wrote:
> > > On Wednesday, August 16, 2023 at 9:42:00 AM UTC-7, olcott wrote:
> > > > On 10/19/2022 5:46 PM, Rock Brentwood wrote:
> > > > > On Tuesday, December 28, 2021 at 1:11:43 AM UTC-6, Jeffrey Rubard wrote:
> > > > >> Maybe not everyone knows that 'Turing-complete' programming languages have several other models equivalent to the Turing machine. Could you 'rate' the different formalisms?
> > > > >> 1) Turing Machines
> > > > >> 2) Lambda Calculus
> > > > >
> > > > > Lambda Calculus with infinitary terms (and the conditional operator).
> > > > > Notation: x = A, B means (lambda x B) A
> > > > > Notation: A? B: C is B is A is true and is C if A is false
> > > > > Example 1:
> > > > > x = 0, y = 1, x < n? (x = x + 1, y = y*x, x < n? (x = x + 1, y = y*x, x < n? (...): y): y): y
> > > > > where the infinitary term denoted by (...) is an exact replica of (x = x + 1, y = y*x, x< n? (...): y).
> > > > >
> > > > > The value of this expression is n!, the factorial of n, assuming that n is a non-negative integer.
> > > > > The value is 1, if n is a negative integer.
> > > > >
> > > > > Notation: Use L: E as a way to denote the (possibly infinitary) subexpression E by the label L
> > > > > Notation: Use "goto L" as a way to refer to the subexpression that the label L denotes
> > > > > Example 2:
> > > > > x? (y? (z? A: B): C): (z? A: B)
> > > > > may be rewritten as
> > > > > x? (y? goto W: C): goto W
> > > > > W: z? A: B
> > > > >
> > > > > Example 3: Example 1 rewritten with labels and gotos
> > > > > x = 0, y = 1, goto Z
> > > > > Z: x < n? (x = x + 1, y = y*x, goto Z): y
> > > > For my purposes the best formalism would be a variation of a RASP
> > > > machine because this could form a bridge between Turing machines and
> > > > high level languages.
> > > >
> > > > The problem with low level languages such as the Turing Machine
> > > > description languages is that they make understanding the underlying
> > > > algorithm specified in this language infeasibly difficult for any
> > > > complex algorithms.
> > > "Does it occur to you that this 'copypasta' of yours is... perhaps too stupid for the 'hoaxing' purposes you want it to serve?"
> > It does occur to me that your 'routines' are too stupid, often.
> "What's a 'PLO'?"
> "The Palestine Liberation Organization."
> "What does Fatah have to do with computer science?"

"Um... there are Palestinian computer scientists?"
"It's... a slightly obsolescent Palestinian political organization that... doesn't have a CS department?"

On Monday, August 21, 2023 at 2:26:45 PM UTC-7, Jeffrey Rubard wrote:
> On Monday, August 21, 2023 at 8:39:30 AM UTC-7, Jeffrey Rubard wrote:
> > On Friday, August 18, 2023 at 1:13:25 PM UTC-7, Jeffrey Rubard wrote:
> > > On Wednesday, August 16, 2023 at 12:16:22 PM UTC-7, Jeffrey Rubard wrote:
> > > > On Wednesday, August 16, 2023 at 9:42:00 AM UTC-7, olcott wrote:
> > > > > On 10/19/2022 5:46 PM, Rock Brentwood wrote:
> > > > > > On Tuesday, December 28, 2021 at 1:11:43 AM UTC-6, Jeffrey Rubard wrote:
> > > > > >> Maybe not everyone knows that 'Turing-complete' programming languages have several other models equivalent to the Turing machine. Could you 'rate' the different formalisms?
> > > > > >> 1) Turing Machines
> > > > > >> 2) Lambda Calculus
> > > > > >
> > > > > > Lambda Calculus with infinitary terms (and the conditional operator).
> > > > > > Notation: x = A, B means (lambda x B) A
> > > > > > Notation: A? B: C is B is A is true and is C if A is false
> > > > > > Example 1:
> > > > > > x = 0, y = 1, x < n? (x = x + 1, y = y*x, x < n? (x = x + 1, y = y*x, x < n? (...): y): y): y
> > > > > > where the infinitary term denoted by (...) is an exact replica of (x = x + 1, y = y*x, x< n? (...): y).
> > > > > >
> > > > > > The value of this expression is n!, the factorial of n, assuming that n is a non-negative integer.
> > > > > > The value is 1, if n is a negative integer.
> > > > > >
> > > > > > Notation: Use L: E as a way to denote the (possibly infinitary) subexpression E by the label L
> > > > > > Notation: Use "goto L" as a way to refer to the subexpression that the label L denotes
> > > > > > Example 2:
> > > > > > x? (y? (z? A: B): C): (z? A: B)
> > > > > > may be rewritten as
> > > > > > x? (y? goto W: C): goto W
> > > > > > W: z? A: B
> > > > > >
> > > > > > Example 3: Example 1 rewritten with labels and gotos
> > > > > > x = 0, y = 1, goto Z
> > > > > > Z: x < n? (x = x + 1, y = y*x, goto Z): y
> > > > > For my purposes the best formalism would be a variation of a RASP
> > > > > machine because this could form a bridge between Turing machines and
> > > > > high level languages.
> > > > >
> > > > > The problem with low level languages such as the Turing Machine
> > > > > description languages is that they make understanding the underlying
> > > > > algorithm specified in this language infeasibly difficult for any
> > > > > complex algorithms.
> > > > "Does it occur to you that this 'copypasta' of yours is... perhaps too stupid for the 'hoaxing' purposes you want it to serve?"
> > > It does occur to me that your 'routines' are too stupid, often.
> > "What's a 'PLO'?"
> > "The Palestine Liberation Organization."
> > "What does Fatah have to do with computer science?"
> "Um... there are Palestinian computer scientists?"
> "It's... a slightly obsolescent Palestinian political organization that.... doesn't have a CS department?"

"What about the PFLP?"
"Hey guy, this is a theory of computation newsgroup."