What is the minimal set of blocks required to make Scratch Turing complete?

Also, what is the minimal set of blocks required to have access to all the features of Scratch (Assuming we can create costumes, import sounds, as well as create variables and lists as much as we like)?

Really few.

when I receive [ v]
broadcast [ v] and wait
() + () :: stack
[] = [] :: stack
add [] to [ v]
replace item ( v) of [ v] with []
item ( v) of [ v] :: stack

That's all.

NOTE: This is similar to https://scratch.mit.edu/discuss/topic/195968/ but it ISN'T a duplicate. There are different requirements.

Jonathan50 wrote:

Really few.

when I receive [ v]
broadcast [ v] and wait
() + () :: stack
[] = [] :: stack
add [] to [ v]
replace item ( v) of [ v] with []

When you pressed the green flag, nothing would happen because you had no start script. If you added the [when green flag clicked] block then you could make scripts run. But is that turing complete? Because there's no way to subtract…

ScratchMan544 wrote:

When you pressed the green flag, nothing would happen because you had no start script. If you added the [when green flag clicked] block then you could make scripts run.

Oh. Whether it is necessary or not is debatable. You can click on a script. ¯\_(ツ)_/¯

But is that turing complete? Because there's no way to subtract…

There is:

add (5) to [minuend v]
add (2) to [subtrahend v]
add (0) to [difference v]
broadcast [subtract v] and wait

when I receive [subtract v]
replace item (1 v) of [difference v] with (item (1 v) of [minuend v])
broadcast [helper v] and wait

when I receive [helper v]
broadcast <(item (1 v) of [subtrahend v]) = [0]> and wait

when I receive [false v]
replace item (1 v) of [difference v] with ((item (1 v) of [difference v]) + (-1))
replace item (1 v) of [subtrahend v] with ((item (1 v) of [subtrahend v]) + (-1))
broadcast [helper v] and wait

I haven't tested it, but if the lists MINUEND, SUBTRAHEND and DIFFERENCE are empty, and if you run the first script, the first item of DIFFERENCE should be 3 (5 - 2).

Edit: It works

You might find this topic interesting!

Jonathan50 wrote:

Really few.

when I receive [ v]
broadcast [ v] and wait
() + () :: stack
[] = [] :: stack
add [] to [ v]
replace item ( v) of [ v] with []

That's all.

NOTE: This is similar to https://scratch.mit.edu/discuss/topic/195968/ but it ISN'T a duplicate. There are different requirements.

You probably need

when green flag clicked

delete (all v) of [list v]

also. (when gf clicked to start, and delete all to get back to the starting state.)

Jonathan50 wrote:

broadcast <(item (1 v) of [subtrahend v]) = [0]> and wait

You could even have an unlimited amount of conditionals by broadcasting <=>+(some even number). This could also be used for a repeat until, so I'd say that this system is definitely Turing-complete. (except that you forgot (item () of [])).

EDIT: Pesky []

BookOwl wrote:

You probably need

when green flag clicked

delete (all v) of [list v]

also. (when gf clicked to start, and delete all to get back to the starting state.)

Nah. You can run scripts without using the flag. And deletion isn't necessary, replacement is sufficient.

Jonathan50 wrote:

ScratchMan544 wrote:

When you pressed the green flag, nothing would happen because you had no start script. If you added the [when green flag clicked] block then you could make scripts run.

Oh. Whether it is necessary or not is debatable. You can click on a script. ¯\_(ツ)_/¯

But is that turing complete? Because there's no way to subtract…

There is:

add (5) to [minuend v]
add (2) to [subtrahend v]
add (0) to [difference v]
broadcast [subtract v] and wait

when I receive [subtract v]
replace item (1 v) of [difference v] with (item (1 v) of [minuend v])
broadcast [helper v] and wait

when I receive [helper v]
broadcast <(item (1 v) of [subtrahend v]) = [0]> and wait

when I receive [false v]
replace item (1 v) of [difference v] with ((item (1 v) of [difference v]) + (-1))
replace item (1 v) of [subtrahend v] with ((item (1 v) of [subtrahend v]) + (-1))
broadcast [helper v] and wait

I haven't tested it, but if the lists MINUEND, SUBTRAHEND and DIFFERENCE are empty, and if you run the first script, the first item of DIFFERENCE should be 3 (5 - 2).

Edit: It works

Much simpler way:

((5)+(-2))

You forgot to add item () of [] to the list too :P

But what if you want to do 5 - VAR then you are forced to do the method metioned

Jonathan50 wrote:

ScratchMan544 wrote:

When you pressed the green flag, nothing would happen because you had no start script. If you added the [when green flag clicked] block then you could make scripts run.

Oh. Whether it is necessary or not is debatable. You can click on a script. ¯\_(ツ)_/¯

But is that turing complete? Because there's no way to subtract…

There is:

add (5) to [minuend v]
add (2) to [subtrahend v]
add (0) to [difference v]
broadcast [subtract v] and wait

when I receive [subtract v]
replace item (1 v) of [difference v] with (item (1 v) of [minuend v])
broadcast [helper v] and wait

when I receive [helper v]
broadcast <(item (1 v) of [subtrahend v]) = [0]> and wait

when I receive [false v]
replace item (1 v) of [difference v] with ((item (1 v) of [difference v]) + (-1))
replace item (1 v) of [subtrahend v] with ((item (1 v) of [subtrahend v]) + (-1))
broadcast [helper v] and wait

I haven't tested it, but if the lists MINUEND, SUBTRAHEND and DIFFERENCE are empty, and if you run the first script, the first item of DIFFERENCE should be 3 (5 - 2).

Edit: It works

Oh yeah! This reminds me of the lambda calculus, where we create the predecessor function P using the successor function S in a similar manner.
[EDIT: Never mind, this is different…]

-Io- wrote:

Much simpler way:

((5)+(-2))

I know that this has been addressed, but… What if you wanted to do (5)-(-2)?

Actually, a+b is a - (0-b) so you can replace addition with subtraction and still have it be Turing-complete!

CodeLegend wrote:

(except that you forgot (item () of []))

Sorry, that was a mistake. I fixed it now.

jokebookservice1 wrote:

But what if you want to do 5 - VAR then you are forced to do the method metioned

You can use list reporters and add a minus to the beginning of a number, the same way you join strings to bypass the 10240 char limit.

I'm kinda cheating with letter of and delete of, but really, they're essential for string manipulation, and I don't want to play with char[]-like structures. This one isn't possible without both of them, since you can't convert strings to char[].

when I receive [start v]
delete (all v) of [vars v]
add [123] to [vars v] // 123
add [] to [vars v] // Remember you can't replace a non-existing item.
broadcast [negate v] and wait
replace item (1 v) of [vars v] with [-321] // -321. Works with negative numbers
broadcast [negate v] and wait
broadcast (<(item (4 v) of [vars v])=[]>+(4)) and wait // This is because, for some reason,
// the broadcast block ends before the negated number can be added to the list
when I receive [negate v]
delete (all v) of [negate v]
replace item (2 v) of [vars v] with [1]
broadcast (<(letter (1) of (item (1 v) of [vars v]))=[-]>+(0)) and wait

when I receive [0 v]
add [-] to [negate v]
broadcast (<(letter (item (2 v) of [vars v]) of (item (1 v) of [vars v]))=[]>+(2)) and wait

when I receive [1 v]
replace item (2 v) of [vars v] with [2]
broadcast (<(letter (item (2 v) of [vars v]) of (item (1 v) of [vars v]))=[]>+(2)) and wait

when I receive [2 v]
add (letter (item (2 v) of [vars v]) of (item (1 v) of [vars v])) to [negate v]
replace item (2 v) of [vars v] with ((item (2 v) of [vars v])+(1))
broadcast (<(letter (item (2 v) of [vars v]) of (item (1 v) of [vars v]))=[]>+(2)) and wait

when I receive [3 v]
add (negate) to [vars v]

when I receive [4 v]
add ((item (3 v) of [vars v])+(item (4 v) of [vars v])) to [return v]
// -123 + 321 = 198

when I receive [5 v]
broadcast (<(item (4 v) of [vars v])=[]>+(4)) and wait

Demo project: https://scratch.mit.edu/projects/127949334/

We could just switch to just using subtraction. x - (0 - y) == x + y.

ScratchMan544 wrote:

We could just switch to just using subtraction. x - (0 - y) == x + y.

Welp. I made a method for joining strings though.