What a fun discussion!

takuya_miyai · 07-25-2021 02:45 AM

Hi there,

This may not be a topic directly related to our daily projects, but it may be of interest to the AppSheet Creater gathered here.

The other day a customer asked me, “Is AppSheet Turing complete?”

I’m not a computer science major, so I couldn’t give him a quick answer right then and there.

At the time, I thought it met many of the requirements, but given the loop processing, it might not be Turing-complete.
However, because of the Loop processing with Grouped Action that @Steve taught us, I now think that AppSheet is Turing-complete.

I’d like to hear your opinions as well.

WillowMobileSys

Exactly right! And I suspect that this is becoming a new buzzword and marketing ploy with no real value.

One article had this quote: “If a language is not Turing complete, there are computational problems it cannot solve. So, purely from a view internal to the language, you can’t necessarily do everything you want.”

Which computational problems can’t the language solve? They may not be important.

Additionally, languages are purpose specific anyway … and some with the same purpose solve certain problems better than others. For example, you wouldn’t use javascript to write a desktop application and HTML is better at object placement on a page than javascript. So, a language being “Turing Complete” doesn’t really place much weight on its usefulness. In fact, even the simplest of apps will use the advantages of several languages together to solve the problems it needs.

I’ll repeat that hardware is the limiting factor with all languages. So here is an interesting simple question…

Can a computer ADD?

View solution in original post

WillowMobileSys

There are two issues with this question.

One is that even though AppSheet is built on top of well-known languages that are considered “Turing Complete”, AppSheet only surfaces certain features and functions of those languages which may very well prevent AppSheet from being considered “Turing complete”. But it could be!

The other bigger issue is that no computer in existence today is “Turing Complete”. They are all limited by internal memory. So, while languages are “Turing Complete” in theory and maybe by mathematical proof, there is no physical way to demonstrate it!

takuya_miyai

Hi, @WillowMobileSystems

Thank you for your valuable input.
I guess the answer depends on each person’s definition of “turing-complete”.

Even if AppSheet is essentially turing-complete, I can understand that unlimited feature opening would be a detriment when considering the use of Citizendeveloper.
I hope that the features will become increasingly sophisticated and powerful for everyone.

By the way, Satya tweeted that he achieved turing-completeness in Excel, so turing-completeness may become the norm not only in AppSheet, but also in the world of no-code on cloud platforms.

WillowMobileSys

Exactly right! And I suspect that this is becoming a new buzzword and marketing ploy with no real value.

One article had this quote: “If a language is not Turing complete, there are computational problems it cannot solve. So, purely from a view internal to the language, you can’t necessarily do everything you want.”

Which computational problems can’t the language solve? They may not be important.

Additionally, languages are purpose specific anyway … and some with the same purpose solve certain problems better than others. For example, you wouldn’t use javascript to write a desktop application and HTML is better at object placement on a page than javascript. So, a language being “Turing Complete” doesn’t really place much weight on its usefulness. In fact, even the simplest of apps will use the advantages of several languages together to solve the problems it needs.

I’ll repeat that hardware is the limiting factor with all languages. So here is an interesting simple question…

Can a computer ADD?

WillowMobileSys

No takers on my challenge question?

The answer is…NO…computers cannot add! More precisely they cannot add just any arbitrary numbers. The reason is due to the limit of memory. I can give a computer a set of numbers to add where the result is large enough the computer cannot store it.

By the way, this also means a computer cannot multiply, divide or subtract - in the full technical sense.

The memory limitation is also the reason why we have collective computing - the idea that a single computer cannot solve a problem but we can break it up into several smaller pieces giving each of those to several computers to solve the smaller piece and then HOPEFULLY can combine the sub results together in the end for a final result.

MultiTech

What a fun discussion!

Brian_Morgan

Can a computer ADD?

I too am not a computer scientist, but I spent a good chunk of my career decades ago flipping bits on a IBM 1130, PDP-8, PDP-11, and all kinds of various 8-bit microprocessors, well before the IBM PC made its debut.

Back then it was common for cash-strapped small businesses to write or purchase floating point arithmetic emulators in the form of a library – no need to spend thousands on a Floating Point Unit (FPU) when it could be emulated in software. Of course, the library was much slower but it got the job done.

Every processor I’ve programmed, going way back in time, had two important instructions: Exclusive-Or (XOR) and Shift Register (SHL/SHR). I can quite easily perform integer addition and multiplication with those two instructions (plus some conditional branch instructions).

But I see your point. If you don’t have XOR or SHL/SHR, but you do have the ability to perform a LOOKUP, then you are memory-limited.

Good discussion!
Brian

Steve

Wow, that is old-school! I love it!