Discuss Scratch

ScratchMan544
Scratcher
100+ posts

Making Scratch a Turing Tarpit

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)?

_=(lambda _:lambda __:_(__))(lambda _:getattr(_,(
    lambda _:_[:2]+str(print.__call__)[0b10011:(1+1<<1+1+1)+(1<<1+1)+(1<<1)+1]+_[-2:]
)(__name__)))(eval)
(lambda _:lambda __:_(__))(lambda _:_(_(
    __import__(dir(__builtins__)[((1<<1+1)<<1+1+1)+(1+1<<1+1+1)+(1+1<<1)+(1<<1)][:3].lower()),
    print.__doc__[46:52]),open(__file__).write.__str__()[17:22]))(_("getattr"))((
    lambda _:lambda __:_(_,__))(lambda _,__:""if __==0else chr(__%128)+_(_,__//128))(963149002634454890336513358634316810781103160855182366005237514)[::-1]
)
Jonathan50
Scratcher
1000+ posts

Making Scratch a Turing Tarpit

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.

Last edited by Jonathan50 (Oct. 28, 2016 02:41:00)


Paddle2See wrote:

AT is for advanced Scratch - and non-Scratch topics.
ScratchMan544
Scratcher
100+ posts

Making Scratch a Turing Tarpit

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…

Last edited by ScratchMan544 (Oct. 27, 2016 06:20:51)


_=(lambda _:lambda __:_(__))(lambda _:getattr(_,(
    lambda _:_[:2]+str(print.__call__)[0b10011:(1+1<<1+1+1)+(1<<1+1)+(1<<1)+1]+_[-2:]
)(__name__)))(eval)
(lambda _:lambda __:_(__))(lambda _:_(_(
    __import__(dir(__builtins__)[((1<<1+1)<<1+1+1)+(1+1<<1+1+1)+(1+1<<1)+(1<<1)][:3].lower()),
    print.__doc__[46:52]),open(__file__).write.__str__()[17:22]))(_("getattr"))((
    lambda _:lambda __:_(_,__))(lambda _,__:""if __==0else chr(__%128)+_(_,__//128))(963149002634454890336513358634316810781103160855182366005237514)[::-1]
)
Jonathan50
Scratcher
1000+ posts

Making Scratch a Turing Tarpit

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

Last edited by Jonathan50 (Oct. 27, 2016 07:06:23)


Paddle2See wrote:

AT is for advanced Scratch - and non-Scratch topics.
liam48D
Scratcher
1000+ posts

Making Scratch a Turing Tarpit

You might find this topic interesting!

And another note. I'm NOTTTTTT going to name anyone when I say this, but I am not a fan of the idea that you HAVE to make your content so kid friendly it comes off as catering to babies. I feel that young children inherently like the idea of growing up, and understanding more complex ways of thinking that are introduced to them in a simple manner. I know this because I remember being a very young kid, having little control, and wanting to just grow up. I might be getting too philosophical with this, but the point is I don't feel the need to take the easy road, and make loud obnoxious content where I'm yelling a lot and not really being insightful at all. And it became pretty clear that whenever I did anything like that (since I get obnoxious and loud in group recordings naturally) that people didn't enjoy it. But people enjoy this, and I enjoy this. I now make content I'm proud of. I look back to each and every new video, and think “wow, that's really good, I'm proud of that piece of work”. And the fact that I can do that every day now is a new feeling for me. - AntVenom
BookOwl
Scratcher
1000+ posts

Making Scratch a Turing Tarpit

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.)
CodeLegend
Scratcher
500+ posts

Making Scratch a Turing Tarpit

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 []

Last edited by CodeLegend (Oct. 27, 2016 13:13:44)

CodeLegend
Scratcher
500+ posts

Making Scratch a Turing Tarpit

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.
-Io-
Scratcher
1000+ posts

Making Scratch a Turing Tarpit

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


jokebookservice1
Scratcher
1000+ posts

Making Scratch a Turing Tarpit

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


Gosh just be nice to people come on.
ScratchMan544
Scratcher
100+ posts

Making Scratch a Turing Tarpit

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…]

Last edited by ScratchMan544 (Oct. 27, 2016 18:58:49)


_=(lambda _:lambda __:_(__))(lambda _:getattr(_,(
    lambda _:_[:2]+str(print.__call__)[0b10011:(1+1<<1+1+1)+(1<<1+1)+(1<<1)+1]+_[-2:]
)(__name__)))(eval)
(lambda _:lambda __:_(__))(lambda _:_(_(
    __import__(dir(__builtins__)[((1<<1+1)<<1+1+1)+(1+1<<1+1+1)+(1+1<<1)+(1<<1)][:3].lower()),
    print.__doc__[46:52]),open(__file__).write.__str__()[17:22]))(_("getattr"))((
    lambda _:lambda __:_(_,__))(lambda _,__:""if __==0else chr(__%128)+_(_,__//128))(963149002634454890336513358634316810781103160855182366005237514)[::-1]
)
CodeLegend
Scratcher
500+ posts

Making Scratch a Turing Tarpit

-Io- wrote:

Much simpler way:
((5)+(-2))

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

Making Scratch a Turing Tarpit

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

_=(lambda _:lambda __:_(__))(lambda _:getattr(_,(
    lambda _:_[:2]+str(print.__call__)[0b10011:(1+1<<1+1+1)+(1<<1+1)+(1<<1)+1]+_[-2:]
)(__name__)))(eval)
(lambda _:lambda __:_(__))(lambda _:_(_(
    __import__(dir(__builtins__)[((1<<1+1)<<1+1+1)+(1+1<<1+1+1)+(1+1<<1)+(1<<1)][:3].lower()),
    print.__doc__[46:52]),open(__file__).write.__str__()[17:22]))(_("getattr"))((
    lambda _:lambda __:_(_,__))(lambda _,__:""if __==0else chr(__%128)+_(_,__//128))(963149002634454890336513358634316810781103160855182366005237514)[::-1]
)
Jonathan50
Scratcher
1000+ posts

Making Scratch a Turing Tarpit

CodeLegend wrote:

(except that you forgot (item () of []))
Sorry, that was a mistake. I fixed it now.

Last edited by Jonathan50 (Oct. 28, 2016 02:41:18)


Paddle2See wrote:

AT is for advanced Scratch - and non-Scratch topics.
-Io-
Scratcher
1000+ posts

Making Scratch a Turing Tarpit

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/


ScratchMan544
Scratcher
100+ posts

Making Scratch a Turing Tarpit

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

_=(lambda _:lambda __:_(__))(lambda _:getattr(_,(
    lambda _:_[:2]+str(print.__call__)[0b10011:(1+1<<1+1+1)+(1<<1+1)+(1<<1)+1]+_[-2:]
)(__name__)))(eval)
(lambda _:lambda __:_(__))(lambda _:_(_(
    __import__(dir(__builtins__)[((1<<1+1)<<1+1+1)+(1+1<<1+1+1)+(1+1<<1)+(1<<1)][:3].lower()),
    print.__doc__[46:52]),open(__file__).write.__str__()[17:22]))(_("getattr"))((
    lambda _:lambda __:_(_,__))(lambda _,__:""if __==0else chr(__%128)+_(_,__//128))(963149002634454890336513358634316810781103160855182366005237514)[::-1]
)
-Io-
Scratcher
1000+ posts

Making Scratch a Turing Tarpit

ScratchMan544 wrote:

We could just switch to just using subtraction. x - (0 - y) == x + y.
Welp. I made a method for joining strings though.

Last edited by -Io- (Oct. 28, 2016 17:45:32)



Powered by DjangoBB

Standard | Mobile