What Is the Definition of Turing Complete? #Bitcoin and #Cryptocurrency Q&A

Learn about what a Turing complete programming language is and why it's more difficult to make a program Turing incomplete. Bitcoin is Turing incomplete whereas Ethereum is Turing complete.
#TuringComplete #BitcoinEducation #EthereumEducation

Chapters
0:00 The life of Allen Turing
0:48 Could you please explain in plain English what is meant by a computer program being or not being Turing complete
1:49 Important characteristics of Turing complete programs
2:29 Turing incomplete programs
3:18 Turing complete systems, while they can express any possible program and are very flexible, we never know if they are going to finish running

COMMENT below and let us know what you think of the video. Post your follow-up questions there too!

You can also learn from one of aantonop's many books about bitcoin, ethereum, and open blockchains. Andreas has written three technical books for developers about blockchain technology, Mastering Bitcoin, Mastering Ethereum, and Mastering the Lightning Network published by O’Reilly Media. He’s also written The Internet of Money Series books, which explain why bitcoin, ethereum, and open blockchains matter.

From Andreas: You may already know that my mission is to educate as many people as possible about #Bitcoin and open blockchain technologies. Watching these videos and sharing them with others is a big part of that. Thank you for being part of this mission.

***Learn More From Andreas**

***Connect with Andreas on Socials***

Thanks for watching, sharing, and subscribing!

[BarziniNwa]

Haha! I'm currently reading your book with Gavin wood and I paused to come watch a video on Turing completeness just to get a broader understanding. Imagine my awe when I got to the end and I hear “Hi, I’m Andreas Antonopoulos…” 😁 you rock!

[motionislife]

This video is really a good Turing-incomplete one, :) I knew I'll get some value within a short period of time....those videos with infinite loop (takes forever to finish) does not value my life...thank you so much!

[rigell]

Thank you so much for all that you do Andreas.

[vroomerlifts]

I literally was reading your ETH book and searched what Turing complete actually meant and saw your video. :D

[markcarter]

Thanks for such a great explanation👏👏👏

[Manvillebrady]

Second time watching this video after seeing it a couple months ago. I stumbled onto The Imagination Game, a movie about Adam Turning cracking the German Enigma Machine of WWII, on PBS last night and realized this is the guy Andreas was referring to in this vid. Good stuff! Great movie. Sad commentary!

[MrGheller]

Andreas, what software(s) did you use to make this audio video?

[locusf]

The Turing completeness of Ethereum comes down to the JUMPI instruction (0x57 in yellow paper, appendix H, page 33). This is called conditional branching which in not-so-plain english means that the program is turing complete when it satisfies conditional branching. The loop and recursion are just something that follows from this.

[danielm.]

Strictly speaking, I don‘t think you answered the question in this video. To make it quick, a model of computation (models are e.g. turing machines themselves, or programming languages like C, anything for which a meaningful sense of what it means to compute something can be defined) is called turing complete if it can theoretically compute any function that could also be computed by a turing machine.

For instance, C is turing complete, turing machines are trivially turing complete, Bitcoin script is not turing complete.

Interesting question: How do you prove something turing complete? The usual way to do it is to formulate a special program, or something comparable (in case you arent talking about a programming language) which interprets programs from a language which you already know is turing complete and computes their result. Then you can just run any program from the turing complete system and yield the result, hence computing the same, so you know your thing is turing complete, too.

Now you might ask yourself what can turing machines compute, and theres a definition for that, but the science community is confident that turing machines can compute anything that a human could, by hand, or thinking through the process, hence anything you can imagine. This is called the church-turing-hypothesis and can not be proven until we have a clear understanding what humans can and cannot do.

[alexwolf]

Could u pls give real life examples
What do you mean program runs for ever ?
Or what happens when program stops running
Sorry! I don't have a background in computers

[WakeRunSleep]

Soo, bitcoin is or is not Turing Complete?

[kenambo]

Seriously is there anything Andreas doesn't know?

[johann-sebastianbach]

Thank you for this explanation! According to my knowledge Touring was not “gay” but he was homosexual.