Favorite computation formalism? (The "Best Test" for CS)

[Jeffrey Rubard]

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?

Go for it!
Jeff Rubard

[Jeffrey Rubard]

Any ideas on the comparative utility of the formal systems for computation?

[Ben Bacarisse]

2 and 4 are very close. For my (undergraduate) dissertation I
implemented a functional language (syntactical sugar for the lambda
calculus) using "lambda abstraction" to produce combinators forms. The
idea was not mine, of course. It was based on a paper by Turner in
Software--Practice and Experience. It was something like "A New
Implementation Technique for Functional Languages".

--
Ben.

[Ben Bacarisse]

Not easy as they compare differently according to different criteria. I
like 2 and 4 and have not heard of 6, but that's a preference based on
intellectual elegance.

For making computability arguments I like very simple register machines
presented as diagrams. TMs come a close second as they are, for most
people, more natural than having unbounded registers.

--
Ben.

[Charlie-Boo]

Rate based on what?
The simplest conceptually is not listed: a finite state machine (FSM) plus 2 stacks.
The smallest in a way is Combinatory Logic.
The easiest is any programming language - I like PHP.

Note that Lambda Calculus might not actually qualify.
I once wrote software to,
1. Generate Lambda Expressions.
2. Execute each.
3. Determine the function being calculated.
All of the functions were monotonic!
Years later I read they're having a hard time representing non-monotonic functions.
But then they said someone figured out how to do it.
Who knows?

C-B

[Charlie-Boo]

On Tuesday, December 28, 2021 at 2:11:43 AM UTC-5, Jeffrey Rubard wrote:

Here's a better question:
There are two obvious models of computing:
A. Programming languages: You execute it.
B. Proof Systems: You search for instances of it.
To generate the prime numbers you express it:
w(x) is x>1^~(ey)(ez)(y>1)&(y<x)&(y*z=x)
then generate theorems
and look for theorems of the form w(...) so ... is a prime number.

1. What is the relationship between A and B?
2. Are there any other types of models of computing?
Are all of 1-7 of form A or B?

C-B

[John Forkosh]

Ben Bacarisse <ben.u...@bsb.me.uk> wrote:

> Jeffrey Rubard <jeffreyda...@gmail.com> writes:
>
>> '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?
>
> Not easy as they compare differently according to different criteria.

Yeah, the different models are kind of "tools", e.g., I'm particularly
interested in domain theory, whereby the lambda calculus is typically
the most useful such tool. By the way, I'm also interested in linear
logic, particularly the C*-algebraic formulation in Girard's geometry
of interaction series of papers. But how, exactly, is it a general
model of computation (references would be great)?

> I like 2 and 4 and have not heard of 6, but that's a preference based
> on intellectual elegance.
>
> For making computability arguments I like very simple register machines
> presented as diagrams. TMs come a close second as they are, for most
> people, more natural than having unbounded registers.

--

John Forkosh ( mailto: j...@f.com where j=john and f=forkosh )

[Ben Bacarisse]

John Forkosh <for...@panix.com> writes:

> Ben Bacarisse <ben.u...@bsb.me.uk> wrote:
>> Jeffrey Rubard <jeffreyda...@gmail.com> writes:
>>
>>> '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?
>>
>> Not easy as they compare differently according to different criteria.
>
> Yeah, the different models are kind of "tools", e.g., I'm particularly
> interested in domain theory, whereby the lambda calculus is typically
> the most useful such tool. By the way, I'm also interested in linear
> logic, particularly the C*-algebraic formulation in Girard's geometry
> of interaction series of papers. But how, exactly, is it a general
> model of computation (references would be great)?

I didn't know about linear logic. In interesting.

--
Ben.

[Jeffrey Rubard]

Good suggestions!

[Jeffrey Rubard]

Not that Turing, Church, Post, Curry, Kleene, Herbrand, or Goedel could "take you up" on them.
(Jean-Yves Girard, or one of his epigones? Maybe.)

[Jeffrey Rubard]

But why not keep it going. What do people think of the Post Correspondence Problem?
What is its "practical upshot"?

[Jeffrey Rubard]

That discussion of the 'halting problem' could halt?

[Jeffrey Rubard]

(PCP actually says something deep. No, not the drug; pretty much exactly like that.)

[B.H.]

On Tuesday, December 28, 2021 at 2:11:43 AM UTC-5, Jeffrey Rubard wrote:

I will share an opinion: Turing machines, which are often discussed and the most popular I believe, are also the best ones. I don't know all of the other programming language (/etc.) that you mentioned, but the problem with most of them, e.g., C++ and (various versions of) descriptive complexity, is that there is no simple and non-arbitrary step counter. The discreteness and uniformity of steps in Turing machines is what makes them great...you either move from one transition state to another one, or you don't, and (neglecting oracle-related issues) it always costs one step and that makes sense. I don't think any other programming languages incorporate this graph-theory-based feature, simply because any such language that did would be too similar to Turing machines themselves.

Maybe I am biased because I like complexity theory; aside from the practical concerns of a programmer, I don't know of any languages that present any advantage at all over Turing machines. That doesn't mean there aren't any, of course.

-Philip White (philip...@yahoo.com)

[Jeffrey Rubard]

Although we are not the 'world's greatest experts', I guess I agree with you. The alternate formalisms are 'technically equivalent' and offer evidence for the Church-Turing Thesis but they did not have the 'practical' effect of Turing's work. (Life can be like that, too. You *could* write logical formulae in Frege's "Concept-Script" but Peano's notation is much easier...)

[B.H.]

If you're the same Jeffrey Rubard from the other thread, I didn't like your post and would prefer not to speak with you again at length in the future.

You are correct that "we are not the 'world's greatest experts,'" in the sense that I am not a true expert in math/CS; I don't have a Ph.D. and don't know everything that such a highly formally educated person would know. At the same time, I am the world's greatest mathematician and computer scientist. The only way that could be mistaken is if other mathematicians/CS people have been very quiet about announcing their breakthrough discoveries. My disclosures about the Hodge Conjecture, Stephen Cook's problem, and PH = PSPACE establish this point clearly. If you or others on here like Ben Bacarisse had any training at math/CS and the understanding that criticizing my breakthroughs without reading them demonstrates laziness and disingenuousness (not to mention a seeming lack of ability to read mathematical arguments efficiently), then you would acknowledge this clear fact, or maybe stay silent about my talent.

-Philip White

[B.H.]

(It is possible that another CS person, Kaveh Ghasemloo, thought of and was announcing his understanding of PH = PSPACE on CS.se; some of my CS breakthroughs are correct and announced but not published in public anywhere. I am claiming that my announcement and my clearly established honesty (I think; I am honest) and understanding of logic demonstrates that I am telling the truth about breakthroughs that I've announced but not published the details of.)

[Jeffrey Rubard]

Wow, that's pretty special. (Maybe do less "pleading" in open sewers like Usenet in the future; it used to make me look stupid when I did it years ago.)

Jeff Rubard

[B.H.]

So the fairly obvious response is: I don't care about your opinion of my Usenet posts during a tough situation where I have no other good choice, don't care if you don't think my Usenet posts sound dominant enough, and would recommend that if you don't want to read my posts about human rights abuses that you just be silent and keep to yourself or other posters. AFAIK you haven't crossed the line into doing anything illegal like some, but insulting people who are in extreme distress, including with mild anti-disabled innuendo, is not a great idea...if you faced a disaster someday, you would want to be non-anti-supported by people who don't fully relate to your situation in a deep way. The possibility that you could and your associated preparedness level could be seen as associated with strength and good fortune; what's your expected value of safety each day (it's related to how supported you would be in case of misfortune, I assert), and how does that affect how others interact with you and pay you on the job? If you are doing well in that regard, you certainly won't be unhappier...not that you have to conduct yourself like Peter Olcott or Daniel P. or me if you don't feel like it.

-Philip

[Jeffrey Rubard]

What you're writing is fucking nuts.

[B.H.]

If that is your opinion you are welcome to it; why don't you not start an insult match with me and not answer me instead? If my writing is so incomprehensible to you and looks like gibberish in your mind, why spend your time claiming that it is indecipherable and thus "nuts?" There are plenty of other threads to amuse the unintelligent. You should stop responding to me. I am writing to end the insult match, which I technically don't yet consider to be harassment and thus illegal on your part--I see your insults as "not sufficiently insulting" according to me to qualify as non-consensual and across the line in my eyes--and thus I don't believe I am at risk of committing a crime (i.e., harassment). I assert that responding with mild insults to persuade someone else to stop talking and insulting people is not harassment, particularly when it doesn't constitute the start to the fight.

I won't be surprised if you leap to be "wij2," harassment criminal extraordinaire also. I am advising against this. You ought to be polite or be silent.

If that is also "gibberish" to you, you might want to study some basic English...there are dictionaries and sentence diagramming books available, as any US middle school graduate ought to know.

In case you're wondering, I insult you a little more harshly, though never too harshly, because I dislike anti-disabled rhetoric. Public insults to hurt disabled rights are just about always dumb.

[wij]

What are you talking about? Jeffrey is idiot. I understand what you say and
totally on your side.

[Jeffrey Rubard]

Guys, it's 2022. You might need new "bits".

[Rock Brentwood]

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

[Ben Bacarisse]

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.

[Paul N]

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

[Jeffrey Rubard]

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

[Rock Brentwood]

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.

[Andy Walker]

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

[olcott]

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

[Jeffrey Rubard]

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

[Jeffrey Rubard]

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

[Jeffrey Rubard]

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

[Jeffrey Rubard]

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

[Jeffrey Rubard]

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