Gold collapsing. Bitcoin UP.

[freetrader]

https://www.reddit.com/r/btc/comments/9tydso/an_eli5_on_bitcoin_script_and_turing_completeness/

 

[Norway]

LOL, I'm looking at that paper more closely and it seems pretty wack. Has errors and inconsistent notation and makes little sense as far as I can tell.

Let's be clear, you cannot execute the same section of script over and over again, you can't copy non values to the stack or alt-stack. So you cannot for example have some section of code executed N number of times where N is the result of some previous calculation. You can do conditional execution, so you can have something later in your script depend on results earlier.

You can have a really long script where if you want something done 8 times you can have 8 sections of code do that, because you knew in advance you wanted it done 8 times, which is what he seems to show in that paper, with misleading/wrong comments like "Loop until Y = X ", and "end of loop/Start of next 6", when what is really happening is conditional execution of a section of code 1 time, and then repeated sections of code like that.

You just spent 180 words avoiding my simple questions. If you believe that looping in bitcoin is not unbounded and therefore not Turing complete, you should say so clearly. (But you would be wrong.)

If you want to address the efficiency of bitcoin as a Turing machine, you should do that. Craig would still be right.

To me, it looks like you are desperately grasping for straws because you don't want Craig Wright to be right.

EDIT (after your edit):

You seem to go down the path to try to prove that bitcoin is not Turing complete, while not stating it clearly.

but Y must be less than 10.

You have highlighted this, but I still have to guess your position. Let's drill down:
Are you saying that bitcoin is not Turing complete because the upper limit for the number of loops have to be defined before they are executed? (Please, try to answer my question and not avoid it.)

 

[trinoxol]

To me the interesting question is: What can be built with the script system?

It is well understood that unbounded computations are not supported in a single script and that any bounded computation is supported. I don't know of anyone who would dispute this.

That makes certain conditions practical and others impractical. Indeed, efficiency is the key point. 1 MB scripts are 5000x more expensive than 200 byte scripts.

My feeling is that any real world product will need fairly small scripts. There will be no (frequent) need to loop 1000 times.

Likely, most practical scripts will be loop free. There's going to be some sequential logic and some boolean conditions. Maybe a little parsing of data in fairly easy ways. For example, the R puzzle technique requires splitting a signature. No loops there and just a few operations.

Craig is absolutely correct but it doesn't mean very much in practical terms. But it's a great thing to create strawmen around and attack things that he never meant to say.

 

[Norway]

As far as I know, Dr. Craig Wright was the first person to point out that bitcoin is Turing complete, and he did it in this video. This does not fit the narrative of the anti-Craig cult. If he is a fake, he should not have deeper insights into the inner workings of the bitcoin system than the self-proclaimed bitcoin experts.

So they fight it in any way they can. Not because they care about Turing completeness in bitcoin, but because they don't want to give Craig the respect he deserves.

 

[Norway]

This anti-Craig cult behaviour was also on full display when I pointed out to @Peter R that there was a "bug" in the bet he had with Craig. Peter invented a new dimension sci-fi-style with a known future (conditional probability where the condition was a known future) to make the logic in his own bet work. Aussie Man Bad syndrome is real.

 

[Zarathustra]

Massively Multiplayer Decentralized Turing Complete Bitcoin (MMDTCB)
Sounds great ;-)

 

[Zarathustra]

Conversation with our very own pro technology/anti cultism representant @digitsu.

 

[cypherblock]

You just spent 180 words avoiding my simple questions.
...

I'll do this thread a favor by not responding to your questions about me, my agenda, etc. Let's talk bitcoin/turing, eh?

Are you saying that bitcoin is not Turing complete because the upper limit for the number of loops have to be defined before they are executed?

It is a limitation but if we stick to purely academic formulations, we can say, "we have an unbounded script length" or something. Typically the requirements of turing completenes say something like "A form of conditional repetition or conditional jump".

As I've shown, by copying sections of code we can get a kind of conditional repetition. But my jump or branching was pretty limited. For example when the top of the stack is 0 it skips the remaining code sections, however, what if we needed to have a second set of iterations?

Or another claim was:

"One necessary condition is a loop with a maximum iteration count that is not determined ahead of the iteration, or recursion where the maximum recursion depth is not determined ahead. " (also from here)

Which, I guess maybe one can challenge by saying the iterations continue indefinitely (if needed)??

I've read that a single instruction set like "subtract and branch if zero" can be said to be Turing complete. But the branching again maybe a challenge.

Perhaps a better way to prove something closer to Turing completeness in Bitcoin script execution, would be to just see if it can mimic a Turing machine in the classic sense (yes you can consult your wiki page now) of a: tape, a head, a state register, and a finite table of instructions (if in state x, and head is at y, the either erase or write a symbol, move the head, switch to new state).

Then we could see if it can satisfy the conditions of a universal turing machine a well.

Also remember we are talking about simply computing a value and putting it on the stack. That is your output. It doesn't get recorded anywhere or used elsewhere. So pretty academic formulation in the end.

 

[Richy_T]

When assessing ideas, he's the only one I've seen saying Bitcoin is Turing complete, the paper he copied just supports that claim, and to my point you'd rather argue over the semantics of plagiarism than challenge the idea. It's almost like you telling us what is important and where we should put attention.

Professional hint I already know

The problem is that it does not. Because Bitcoin wasn't around when the paper was written and Craig's additions simply do not properly connect the original paper to the "Turing completeness" of Bitcoin. It's all in the medium article.
[doublepost=1569547437][/doublepost]

You can regard this as Turing completeness and it's true.

https://en.wikipedia.org/wiki/Halting_problem

A key part of the proof was a mathematical definition of a computer and program, which became known as a Turing machine; the halting problem is undecidable over Turing machines.

Lacking loops, the halting problem is not an issue and thus there is no Turing machine.
[doublepost=1569547614][/doublepost]

because the upper limit for the number of loops have to be defined before they are executed?

It's not a loop if it don't loop, G.

 

[Norway]

I get it @cypherblock. You don't have the competence to decide if bitcoin is Turing complete or not. It's ok to say "I don't know".

 

[Richy_T]

But it's a great thing to create strawmen around and attack things that he never meant to say.

The paper is literally called "A Proof of Turing Completeness in Bitcoin Script”.

 

[Norway]

It's not a loop if it don't loop, G.

I think we can both agree that circular reasoning is both true and useless at the same time.
[doublepost=1569548458][/doublepost]Maybe this question can turn on some lightbulbs here:
How many times can bitcoin loop?

 

[Richy_T]

I think we can both agree that circular reasoning is both true and useless at the same time.

Then kindly don't refer to things that aren't loops as loops.
[doublepost=1569548711][/doublepost]

How many times can bitcoin loop?

In script or in some other irrelevant manner?
[doublepost=1569549561,1569548510][/doublepost]@trinoxol, by the way, I agree that Turing completeness may not be something we should be particularly concerned about in Bitcoin. This is more discussion surrounding the medium article and the credibility of Craig Wright.

 

[Norway]

In script or in some other irrelevant manner?

By unrolling the loop in script. How many times?

 

[AdrianX]

@deadalnix the reason BCH lost most of its value, as it's hovering around 3% of the BTC price, is because you have power. You've succeeded in demonizing BU, and kicking nChain out leaving ABC in charge.

Honestly. You told me face to face, investors don't matter, doing CTOR now is more important that adoption, and I can fork off if I don't like it. FYI, that's not an effective way to build working relationships or scale Bitcoin, I'd recommend you do it by cooperating, looking for a win-win. That 3% is not going to hold not because Core may be correct, it's because you have enough control to screw up BCH and investors are losing confidence.

https://www.reddit.com/r/bitcoincashSV/comments/d9pf4z/abc_bitcoin_core_might_have_been_right/

 

[cypherblock]

You don't have the competence to decide if bitcoin is Turing complete or not. It's ok to say "I don't know".

LOL, you're funny.

Focus.

Is bitcoin turing complete? How might one show that? If it is, can we make use of that somehow? If it isn't is that a big deal?
[doublepost=1569562995][/doublepost]

How many times can bitcoin loop?

It can't loop in the traditional sense at all by going back to some earlier point in the code. As I've shown you can have repeated sections of code that get conditionally executed. As long as you have few limits on the length of script, you can have many many repeated sections. By repeating sections, you can gain the functional equivalence of a loop over that section, bounded in iterations by any script length limits.

 

[Norway]

It can't loop in the traditional sense at all by going back to some earlier point in the code. As I've shown you can have repeated sections of code that get conditionally executed. As long as you have few limits on the length of script, you can have many many repeated sections. By repeating sections, you can gain the functional equivalence of a loop over that section, bounded in iterations by any script length limits.

Lol, resisting every inch. So bitcoin without script length limits, the vision of Satoshi, has an unbounded number of loops that can be unrolled in script.

The anti-Craig cult members are making their denial very visible when put on the spot on the Turing completeness in bitcoin issue. Trying to dance around the facts that Craig was right, and that Bitcoin is Turing complete.

 

[trinoxol]

True. The rest of the thread has some interesting thoughts as well although I certainly do not endorse them.

---

It's pretty amazing how BCH disintegrates at the moment for no reason at all. Who's the dumpster fire now?

 

[freetrader]

I agree that Turing completeness may not be something we should be particularly concerned about in Bitcoin.

When it comes to Bitcoin Script, we absolutely should be.

If you can create an infinite loop then we have a problem that needs to be fixed on the double.

Others have issued challenges before, I'm not going to repeat theirs.

Fact is, Bitcoin Script is NOT Turing complete, Craig's "proof" remains hokum, the whole "Bitcoin is Turing complete" angle is to attract idiots who are easily bamboozled.

This has been a Public Service Announcement.

 

[cypherblock]

Lol, resisting every inch. So bitcoin without script length limits, the vision of Satoshi, has an unbounded number of loops that can be unrolled in script.

The anti-Craig cult members are making their denial very visible when put on the spot on the Turing completeness in bitcoin issue. Trying to dance around the facts that Craig was right, and that Bitcoin is Turing complete.

At almost every remark you resort to tribalism. It is not me against Craig*. The cult is in your mind.

This whole "unrolled in script" thing is sort of bad terminology, and although what I demonstrated is actually the first example of a working version of this kind of thing that I've seen in bitcoin script (feel free to find and post a working example that was done earlier as I'm genuinely curious), anything more complex, like being able to support more than one iterative section would seem to require an inner unbounded repetition of code inside the outer block. Leading to at minimum highly unpractical code and possibly theoretical issues as well.

Lacking the ability to jump is a severe limitation and therefore this must be managed with state trackers, being able to skip unbounded sections of code to reach another nested unbounded section of code when a certain condition is met.

To prove turing completness I think it would be better to show that script can emulate a turing machine (of the universal sort) as I've suggested earlier. That would simply eliminate all questions.

(* that is not to say I haven't argued against him when he says completely wrong shit)