Scratch 2.0 is obviously turing complete do to the unbounded memory provided by lists, but as there is a limitation of 200,000 items in a list, is scratch 3.0 still turing complete?
Currently it appears to be so, (because there isn't a limit to string length, unlike scratch 2.0) but assuming scratch patches this, will scratch 3.0 still be turing complete?

By this logic, one could say that nothing which actually exists is Turing-complete. All computers have a limited amount of memory. Even Scratch 2.0 could only store as much as the hardware would allow. I would argue it's not sensible, therefore, to use the memory requirement, when deciding if a language is Turing-complete.

You are correct, though, that there is no limit to the number of characters you can concatenate using the join block. This is important, because the other method of concatenation (creating a long list of single elements and then reporting the list) won't work anymore due to this new limit.

jokebookservice1 wrote:

By this logic, one could say that nothing which actually exists is Turing-complete. All computers have a limited amount of memory. Even Scratch 2.0 could only store as much as the hardware would allow. I would argue it's not sensible, therefore, to use the memory requirement, when deciding if a language is Turing-complete.

You are correct, though, that there is no limit to the number of characters you can concatenate using the join block. This is important, because the other method of concatenation (creating a long list of single elements and then reporting the list) won't work anymore due to this new limit.

You are confusing a finite state automaton with a turing machine.
The concept of scratch is what we are discussing here, not the actual implementation.
As you said, nothing that actually exists is turing complete, however concepts can be turing complete.
For example, the concept of brainf*** is turing complete, but no implentation can be.
Same with scratch 2.0, the concept of scratch 2.0 is turing complete, but no implentation can be.
The question at hand, is whether or not the concept of scratch 3.0 is turing complete.

Wait, there's a limit on list length now?

thisandagain pls explain this memery

$(".box-head")[0].textContent = "committing AT crimes since $whenever"

has anyone tried a brainflakes interpreter in scratch 3? if you can make one, it's turing complete

WackyKitKat wrote:

has anyone tried a brainflakes interpreter in scratch 3? if you can make one, it's turing complete

It is (to my belief) impossible to make a turing complete brainf*** interpreter in scratch 3 due to the new list limit I have talked about above.

MegaApuTurkUltra wrote:

Wait, there's a limit on list length now?

thisandagain pls explain this memery

Here's the so called “explanation.”
https://github.com/LLK/scratch-vm/pull/1031#issuecomment-379755753

It's another feature that's being removed to support mobile users.
The thing though, is it is easy to workaround it, as you can just use multiple lists.
However it affects whether scratch is turing complete or not.

I'm not sure I concur that Scratch 2.0 was Turing complete.

• Scratch 2.0 was written in Flash, which is a superset of ECMAScript
  
• ECMAScript numbers are represented as doubles
  
• There exists an integer that is too big to be accurately represented by a double
  

Hence, at some point, the list index you attempt to use becomes Infinity?

Thoughts?

jokebookservice1 wrote:

I'm not sure I concur that Scratch 2.0 was Turing complete.

• Scratch 2.0 was written in Flash, which is a superset of ECMAScript
  
• ECMAScript numbers are represented as doubles
  
• There exists an integer that is too big to be accurately represented by a double
  

Hence, at some point, the list index you attempt to use becomes Infinity?

Thoughts?

That is down to implementation, rather than concept, whilst an integer may eventually get too big to be used as a list index, that is down to implementation, but the concept of having no hardcoded limit to list length makes it Turing complete. The choice to include a hardcoded limit makes the concept no longer Turing complete.

bybb wrote:

That is down to implementation, rather than concept, whilst an integer may eventually get too big to be used as a list index, that is down to implementation, but the concept of having no hardcoded limit to list length makes it Turing complete. The choice to include a hardcoded limit makes the concept no longer Turing complete.

You're probably right, but JS/Flash hard-coded their integer limits too – and Scratch chose to use those languages without making a BigNum implementation. How is that different from Scratch hard-coding it in its source code.

I'm a little confused what's the difference between the implementation of Scratch 3.0, and the concept of Scratch 3.0: and how we've decided that the list limit is part of the latter, not (just) the former?

jokebookservice1 wrote:

I'm not sure I concur that Scratch 2.0 was Turing complete.

• Scratch 2.0 was written in Flash, which is a superset of ECMAScript
  
• ECMAScript numbers are represented as doubles
  
• There exists an integer that is too big to be accurately represented by a double
  

Hence, at some point, the list index you attempt to use becomes Infinity?

Thoughts?

It's tricky.
One might say for example that a C program that emulated a Turing machine using the host platform's word size is Turing complete because it could theoretically be recompiled on machines with arbitrarily large memory and arbitrarily large word size. So it would seem that since ECMAScript by its standard is limited to exactly 64 bit floats for numbers, it could not possibly be Turing complete.
However, one might also argue that Scratch 2 is not necessarily tied down to a specific interpreter platform, and that one could make an interpreter for Scratch 2 that could theoretically read arbitrary size list indices out of the project JSON and emulate them. But we can't really say for sure because I don't think Scratch 2 has any sort of “official spec” besides the flash interpreter.

Besides that, one can also abuse hacked blocks to completely avoid list indexing and simply create variables on-the-fly as “list indexes” (the first time you called a hacked {set () to ()} with a variable that doesn't exist, it just gets created). Since variable lookup is string-based that means you can implement string-based bignums for indexing such a “list” and not be subject to any ECMAScript restrictions.

$(".box-head")[0].textContent = "committing AT crimes since $whenever"

MegaApuTurkUltra wrote:

So it would seem that since ECMAScript by its standard is limited to exactly 64 bit floats for numbers, it could not possibly be Turing complete.

Not really, you could use linked lists, for example.

One can use two (infinite) stacks to emulate a list of infinite length, and (infinite) recursion can emulate a stack.
Therefore it is possible using two concurrent scripts to emulate a list.
Here's a demo: https://scratch.mit.edu/projects/257075114/

So scratch 3.0 should be turing complete.

MegaApuTurkUltra wrote:

jokebookservice1 wrote:

I'm not sure I concur that Scratch 2.0 was Turing complete.

• Scratch 2.0 was written in Flash, which is a superset of ECMAScript
  
• ECMAScript numbers are represented as doubles
  
• There exists an integer that is too big to be accurately represented by a double
  

Hence, at some point, the list index you attempt to use becomes Infinity?

Thoughts?

It's tricky.
One might say for example that a C program that emulated a Turing machine using the host platform's word size is Turing complete because it could theoretically be recompiled on machines with arbitrarily large memory and arbitrarily large word size.

I have to say that I disagree with this.
I'm actually mostly interjecting here because I just recently learned about the interesting problems I'm discussing here, and I wanted to share. :P

Any sort of programming language that uses constant-size indices cannot, by definition, access an infinite amount of memory. This includes C, whose specification requires that pointers are a constant size (e.g. 4 bytes). Sure, this constant size can be arbitrarily large, but it is required by the standard that once the program is compiled, pointer size cannot get any larger. The C standard provides no mechanism through which a pointer can index more memory than its constant size allows it to. If I'm not mistaken, the only reason C would be Turing complete is because IIRC there's no restriction on creating infinite stack frames.

Of course, there could be some mechanism outside the C standard that allowed a particular implementation to have e.g. bigint-style pointers.

Of course, this also doesn't really apply to Scratch. As you mentioned, Scratch enables indexing variables through arbitrarily sized “pointers,” so I guess my post is really just about C. It is quite strange to think, however, that C may be less easily Turing complete than intuition would suggest.

TheMonsterOfTheDeep wrote:

MegaApuTurkUltra wrote:

jokebookservice1 wrote:

I'm not sure I concur that Scratch 2.0 was Turing complete.

• Scratch 2.0 was written in Flash, which is a superset of ECMAScript
  
• ECMAScript numbers are represented as doubles
  
• There exists an integer that is too big to be accurately represented by a double
  

Hence, at some point, the list index you attempt to use becomes Infinity?

Thoughts?

It's tricky.
One might say for example that a C program that emulated a Turing machine using the host platform's word size is Turing complete because it could theoretically be recompiled on machines with arbitrarily large memory and arbitrarily large word size.

I have to say that I disagree with this.
I'm actually mostly interjecting here because I just recently learned about the interesting problems I'm discussing here, and I wanted to share. :P

Any sort of programming language that uses constant-size indices cannot, by definition, access an infinite amount of memory. This includes C, whose specification requires that pointers are a constant size (e.g. 4 bytes). Sure, this constant size can be arbitrarily large, but it is required by the standard that once the program is compiled, pointer size cannot get any larger. The C standard provides no mechanism through which a pointer can index more memory than its constant size allows it to. If I'm not mistaken, the only reason C would be Turing complete is because IIRC there's no restriction on creating infinite stack frames.

Of course, there could be some mechanism outside the C standard that allowed a particular implementation to have e.g. bigint-style pointers.

Of course, this also doesn't really apply to Scratch. As you mentioned, Scratch enables indexing variables through arbitrarily sized “pointers,” so I guess my post is really just about C. It is quite strange to think, however, that C may be less easily Turing complete than intuition would suggest.

Where does the C specification require pointers to be a certain size?

C pointers are platform dependent. On a 32 bit machine, sizeof(void*) is 4. On a 64-bit machine, it's 8. We assume that if we have a C compiler for a machine with any amount of memory, the pointer size configured in the compiler for that machine will be large enough to address all of that machine's memory.

$(".box-head")[0].textContent = "committing AT crimes since $whenever"

MegaApuTurkUltra wrote:

TheMonsterOfTheDeep wrote:

MegaApuTurkUltra wrote:

jokebookservice1 wrote:

I'm not sure I concur that Scratch 2.0 was Turing complete.

• Scratch 2.0 was written in Flash, which is a superset of ECMAScript
  
• ECMAScript numbers are represented as doubles
  
• There exists an integer that is too big to be accurately represented by a double
  

Hence, at some point, the list index you attempt to use becomes Infinity?

Thoughts?

It's tricky.
One might say for example that a C program that emulated a Turing machine using the host platform's word size is Turing complete because it could theoretically be recompiled on machines with arbitrarily large memory and arbitrarily large word size.

I have to say that I disagree with this.
I'm actually mostly interjecting here because I just recently learned about the interesting problems I'm discussing here, and I wanted to share. :P

Any sort of programming language that uses constant-size indices cannot, by definition, access an infinite amount of memory. This includes C, whose specification requires that pointers are a constant size (e.g. 4 bytes). Sure, this constant size can be arbitrarily large, but it is required by the standard that once the program is compiled, pointer size cannot get any larger. The C standard provides no mechanism through which a pointer can index more memory than its constant size allows it to. If I'm not mistaken, the only reason C would be Turing complete is because IIRC there's no restriction on creating infinite stack frames.

Of course, there could be some mechanism outside the C standard that allowed a particular implementation to have e.g. bigint-style pointers.

Of course, this also doesn't really apply to Scratch. As you mentioned, Scratch enables indexing variables through arbitrarily sized “pointers,” so I guess my post is really just about C. It is quite strange to think, however, that C may be less easily Turing complete than intuition would suggest.

Where does the C specification require pointers to be a certain size?

C pointers are platform dependent. On a 32 bit machine, sizeof(void*) is 4. On a 64-bit machine, it's 8. We assume that if we have a C compiler for a machine with any amount of memory, the pointer size configured in the compiler for that machine will be large enough to address all of that machine's memory.

I don't think that TheMonsterOfTheDeep is saying that the C standard requires that pointers be some specific size, but that they must have a size. Because pointers have a finite set of possible values, they can only address a finite amount of memory. I'm not a C expert, though.

no swearing

reallyharduser wrote:

no swearing

What swearing?

Edit: Oh, you mean that Turing tarpit language…