Is this minimalist instruction set Turing complete?

  • 7 Replies
  • 2363 Views
*

Zero

  • Eve
  • ***********
  • 1287
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
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.

*

ivan.moony

  • Trusty Member
  • ************
  • Bishop
  • *
  • 1723
    • mind-child
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 »

*

ranch vermin

  • Not much time left.
  • Terminator
  • *********
  • 947
  • 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

  • Eve
  • ***********
  • 1287
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.

*

ivan.moony

  • Trusty Member
  • ************
  • Bishop
  • *
  • 1723
    • mind-child
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`.

*

Zero

  • Eve
  • ***********
  • 1287
Re: Is this minimalist instruction set Turing complete?
« Reply #5 on: October 02, 2018, 03:01:29 pm »
got it

*

ranch vermin

  • Not much time left.
  • Terminator
  • *********
  • 947
  • 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

  • Eve
  • ***********
  • 1287
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.

 


OpenAI Speech-to-Speech Reasoning Demo
by ivan.moony (AI News )
March 28, 2024, 01:31:53 pm
Say good-bye to GPUs...
by MikeB (AI News )
March 23, 2024, 09:23:52 am
Google Bard report
by ivan.moony (AI News )
February 14, 2024, 04:42:23 pm
Elon Musk's xAI Grok Chatbot
by MikeB (AI News )
December 11, 2023, 06:26:33 am
Nvidia Hype
by 8pla.net (AI News )
December 06, 2023, 10:04:52 pm
How will the OpenAI CEO being Fired affect ChatGPT?
by 8pla.net (AI News )
December 06, 2023, 09:54:25 pm
Independent AI sovereignties
by WriterOfMinds (AI News )
November 08, 2023, 04:51:21 am
LLaMA2 Meta's chatbot released
by 8pla.net (AI News )
October 18, 2023, 11:41:21 pm

Users Online

289 Guests, 0 Users

Most Online Today: 363. Most Online Ever: 2369 (November 21, 2020, 04:08:13 pm)

Articles