Is this minimalist instruction set Turing complete?

  • 7 Replies
  • 510 Views
*

Zero

  • Trusty Member
  • ********
  • Replicant
  • *
  • 737
    • Thinkbots are free
Is this minimalist instruction set Turing complete?
« on: October 01, 2018, 03:31:01 pm »
Hi,

I'm wondering whether or not this instruction set is Turing complete. It's meant to be used in a stack-oriented engine.

Code: [Select]
Available instructions:
  * cons
  * head
  * tail
  * bind

CONS
  a b cons
  => (a b)

HEAD
  (a b c) head
  => a

TAIL
  (a b c) tail
  => (b c)

BIND
  (a) b bind b
  => a


Example
=======

Program:
    (tail head) second-element bind
    (a b c d) second-element

Expected:
    b

I intuitively believe that it's Turing complete. What do you think?

The idea beyond this step would be to build an ontology of this mechanism, or to build an "understanding" of it. Then, given a goal, being able to automatically construct a program that fulfils the goal. In this very language of course (in another lang / from the outside, it wouldn't be funny).

Ed: No, there's something wrong. It lacks depth. There should be substitution somewhere.
Thinkbots are free, as in 'free will'.
Check out Hashbag

*

ivan.moony

  • Trusty Member
  • **********
  • Millennium Man
  • *
  • 1153
    • Some of my projects
Re: Is this minimalist instruction set Turing complete?
« Reply #1 on: October 01, 2018, 03:51:33 pm »
A programming language is said to be Turing complete if we can program fully functional Turing machine in it. Another way is to program lambda calculus in it, as it is proven that lambda calculus is Turing complete.

Interesting choice of operators. Look what I managed to do with a similar set of operators (link), but what I lack is simplicity. It's still a bit of awkward, but I'm working on it.
« Last Edit: October 01, 2018, 05:54:07 pm by ivan.moony »
Dream big. The bigger the dream is, the more beautiful place the world becomes.

*

ranch vermin

  • Not much time left.
  • Terminator
  • *********
  • 961
  • Its nearly time!
Re: Is this minimalist instruction set Turing complete?
« Reply #2 on: October 01, 2018, 05:01:53 pm »
Youll have to explain it a bit more if im going to understand this,  what is cons.  bind is assign?  heads and tails is 1 and 0?

*

Zero

  • Trusty Member
  • ********
  • Replicant
  • *
  • 737
    • Thinkbots are free
Re: Is this minimalist instruction set Turing complete?
« Reply #3 on: October 02, 2018, 01:39:52 pm »
Youll have to explain it a bit more if im going to understand this,  what is cons.  bind is assign?  heads and tails is 1 and 0?

Ok, I'll do my best.
The "cons",  "head" and "tail" come from the Lisp world. Except in Lisp, "head" and "tail" are rather named "car" and "cdr" (for some obscure/irrelevant historical reason). Say you have a list of elements a b c and d. Lists are written between parentheses : (a b c d). The "head" of the list is a, and the "tail" of the list is the list (b c d). The "cons" builds a pair. In Lisp, lists are single-linked list at low-level, where "car" always point to a value, and "cdr" points on the next pair, or on "nil" to indicate the end of the list. I think the wikipedia article explains it quite well. Interesting stuff.

A programming language is said to be Turing complete if we can program fully functional Turing machine in it. Another way is to program lambda calculus in it, as it is proven that lambda calculus is Turing complete.

Interesting choice of operators. Look what I managed to do with a similar set of operators (link), but what I lack is simplicity. It's still a bit of awkward, but I'm working on it.

I like it, even though I'm not sure I get it all. I'm ok with ?, but what does ! mean?



I realize that I really lack conditional here, because I don't see how I would implement branching with only this instruction set. I found a nice thread on SO about minimal Lisp primitives.

A very very minimal lisp could be a beautiful thing.
Thinkbots are free, as in 'free will'.
Check out Hashbag

*

ivan.moony

  • Trusty Member
  • **********
  • Millennium Man
  • *
  • 1153
    • Some of my projects
Re: Is this minimalist instruction set Turing complete?
« Reply #4 on: October 02, 2018, 02:53:35 pm »
I'm ok with ?, but what does ! mean?

It's a complement. For expression `"x"."abc"`, `x.!` stands for everything but `abc`.
Dream big. The bigger the dream is, the more beautiful place the world becomes.

*

Zero

  • Trusty Member
  • ********
  • Replicant
  • *
  • 737
    • Thinkbots are free
Re: Is this minimalist instruction set Turing complete?
« Reply #5 on: October 02, 2018, 03:01:29 pm »
got it
Thinkbots are free, as in 'free will'.
Check out Hashbag

*

ranch vermin

  • Not much time left.
  • Terminator
  • *********
  • 961
  • Its nearly time!
Re: Is this minimalist instruction set Turing complete?
« Reply #6 on: October 02, 2018, 03:20:02 pm »
means invert.    I didnt understand btw...  still...

*

Zero

  • Trusty Member
  • ********
  • Replicant
  • *
  • 737
    • Thinkbots are free
Re: Is this minimalist instruction set Turing complete?
« Reply #7 on: October 02, 2018, 03:46:37 pm »
Maybe the answer I'm looking for is rather a subset of an existing language, like Js for instance.
Thinkbots are free, as in 'free will'.
Check out Hashbag