Ai Dreams Forum

Member's Experiments & Projects => General Project Discussion => Topic started by: Zero on October 01, 2018, 03:31:01 pm

Title: Is this minimalist instruction set Turing complete?
Post by: Zero 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
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.
Title: Re: Is this minimalist instruction set Turing complete?
Post by: ivan.moony 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 (https://github.com/ivanvodisek/random-thoughts/blob/master/sequela.md)), but what I lack is simplicity. It's still a bit of awkward, but I'm working on it.
Title: Re: Is this minimalist instruction set Turing complete?
Post by: ranch vermin 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?
Title: Re: Is this minimalist instruction set Turing complete?
Post by: Zero on October 02, 2018, 01:39:52 pm
Quote from: ranch vermin 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?

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 (https://en.wikipedia.org/wiki/CAR_and_CDR) explains it quite well. Interesting stuff.

Quote from: ivan.moony 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 (https://github.com/ivanvodisek/random-thoughts/blob/master/sequela.md)), 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 (https://stackoverflow.com/questions/3482389/how-many-primitives-does-it-take-to-build-a-lisp-machine-ten-seven-or-five).

A very very minimal lisp could be a beautiful thing.
Title: Re: Is this minimalist instruction set Turing complete?
Post by: ivan.moony on October 02, 2018, 02:53:35 pm
Quote from: Zero on October 02, 2018, 01:39:52 pm
I'm ok with ?, but what does ! mean?

It's a complement. For expression `"x"."abc"`, `x.!` stands for everything but `abc`.
Title: Re: Is this minimalist instruction set Turing complete?
Post by: Zero on October 02, 2018, 03:01:29 pm
got it
Title: Re: Is this minimalist instruction set Turing complete?
Post by: ranch vermin on October 02, 2018, 03:20:02 pm
means invert.    I didnt understand btw...  still...
Title: Re: Is this minimalist instruction set Turing complete?
Post by: Zero 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.