Gold collapsing. Bitcoin UP.

[trinoxol]

> To prove turing completness I think it would be better to show that script can emulate a turing machine

Seems fairly straight forward. The left part of the tape is the stack. The right part is the altstack. On top of the stack there's an additional integer for the current state. Then you define an iteration function that pops the current state and current tape value from the stack, examines it with a bunch of ifs and pushes the new state and new tape item to the appropriate stack. This iteration function is then unrolled N times.

> 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.

I think any C-like code can be rewritten to a state machine fairly efficiently. Nested loops would not lead to an exponential increase in unrolled code size.

This is how the "await" language feature found in many modern languages (C#, JavaScript, python) is implemented. This is a mechanical transformation that a compiler can perform. You can see it here:

https://sharplab.io/#v2:CYLg1APgAgTAjAWAFBQAwAIpwKwG5nJQDMmM6AwugN7Lp2YlYBsmAHJiwGIAUAlNbXpCAZgHsATum4BLAHYAXdNPQBedKlxL0AHnRwNSsGH40kQoQEgxkmQvQArVes2Pd+l0ZODzP+tOFSymAOOnqoXma+UUJQAJwcAHQAIgCmADYAhgCeMujB9rz4kdHmAL7e5hblxWUV1dVAA=

I put two nested loops in there and an if. The compiler rewrites it all away into switch+goto (which would become if plus an unrolled loop in Bitcoin script). The meat of this is in the MoveNext function which is compiler generated. MoveNext corresponds to what a single Bitcoin script would contain. There needs to be an outer loop that repeatedly calls MoveNext to move the state machine forward. In Bitcoin Script this can be done by unrolling or by a sequence of transactions.

 

[cypherblock]

>Seems fairly straight forward.

Then you may want to actually code it up in bitcoin script. Be the first !

>I think any C-like code can be rewritten to a state machine fairly efficiently.

Not to dismiss your work but I don't really see how this example pertains to bitcoin script as it contains things like goto, and we can't just say 'it can be unrolled'. Yes state management will be key. We've seen no example of nested loops in bitcoin script that I'm aware of. The approach I used and ones proposed by this paper would seem to require unbounded sections within other unbounded repeated sections. But yeah there may certainly be another way. Some nested loops can be converted to single loop for sure.

 

[Norway]

@cypherblock
The tribalism is you resorting to all kinds of excuses to undermine the facts that bitcoin is Turing complete and that Craig Wright was the first person to point this out.

- You're not convinced. (No matter how much this is proven to you.)
- It's not effective. (Which is beside the point.)
- It's not important. (Which it is, in the matter of giving Craig Wright the respect for his insights into bitcoin's inner workings that he deserves.)

Don't try to brand me as tribalistic when I expose your Aussie Man Bad agenda.

 

[Richy_T]

By unrolling the loop in script. How many times?

None. It's not a loop if it don't loop, G. I thought we'd got past this.
[doublepost=1569591422][/doublepost]

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

Sure. I meant in terms of being something we should want it to have. As you suggest, it was specifically designed not to be so.

 

[cypherblock]

@cypherblock
The tribalism is you resorting to all kinds of excuses to undermine the facts that bitcoin is Turing complete and that Craig Wright was the first person to point this out.

- You're not convinced. (No matter how much this is proven to you.)
- It's not effective. (Which is beside the point.)
- It's not important. (Which it is, in the matter of giving Craig Wright the respect for his insights into bitcoin's inner workings that he deserves.)

Don't try to brand me as tribalistic when I expose your Aussie Man Bad agenda.

The amount of trolling one has to endure here .

The vast majority of my discussion here is on a technical theoretical level largely divorced of discussion of Craig. The record speaks for itself. I've done more here to show bitcoin may be turing complete than you (which is pretty funny considering your attitude towards me).

Please spare us all this ridiculous time wasting back and forth of accusation, attack, trolling. If you want to have interesting discussion on Bitcoin, what can be done with it, theoretical conversations, or just have a fun chat, I'm sure that would be more welcome not only to me but others.

We all get it, you think I'm some super anti-craig guy. Move on.

 

[Norway]

@Richy_T
You can do loops by unrolling them, and I think you understand this. Nitpicking on this is just nitpicking, to use your own circular reasoning.

Whether you unroll the loops or not, is not relevant to the issue of Turing completeness. The point is that the loops are unbounded, unrolled or not.

 

[trinoxol]

We start with arbitrary C code. Now let's assume the "await" rewrite has been performed. Clearly, that's possible. We now have:

struct State { /* arbitrary data for local variables represented as fields */ }

State MoveNext(State oldState) {
switch (state) {
case 0:
SomeCode0();
return new State(...); //capture local variables into return value
case 0:
SomeCode1();
return new State(...); //capture local variables into return value
//etc.
}
}

Iterating this state machine:

State state = ...; //initial state
state = MoveNext(state);
state = MoveNext(state);
state = MoveNext(state);
//unroll as often as you like

This is a finite state machine. Translating "switch" to "if" is simple:

if (state == 0) SomeCode0();
else if (state == 1) SomeCode1();
//etc.

How do we translate the state part? "oldState" becomes the stack contents before the instructions which form "MoveNext". The "return new State(...)" part becomes the stack contents after the "MoveNext" instructions are done.

I started writing an example but it is too much work. I hope the process has been shown. We can use successive rewrites to rewrite any C program into Bitcoin script.

I think Craig understands this procedure. If you are familiar with certain computer science ideas this really is not hard to come up with. Working out the details is a lot of work, though.

Of course, as we all agree I think, a single script is always bounded. No infinite loop can be written inside a single transaction. That makes it, clearly, not Turing complete in the strict definition. If we add an iteration technique such as multiple transactions it becomes truly Turing complete in every sense of the word. Or, we accept that practically useful scripts only require bounded iteration.

Somebody should create a C-like language that is translated to Bitcoin script. A script is, essentially, a function taking arbitrary arguments and returning bool. Like this:

bool main(byte[] pubKey, byte[] signature) {
return hash(pubKey) == pubKeyHash && checksig(pubKey, signature);
}

This language could support loops, helper functions, structs, tuples and many other high level concepts. All of that can be rewritten away.

 

[Richy_T]

@Richy_T
You can do loops by unrolling them, and I think you understand this. Nitpicking on this is just nitpicking, to use your own circular reasoning.

Whether you unroll the loops or not, is not relevant to the issue of Turing completeness. The point is that the loops are unbounded, unrolled or not.

No you can't. Unrolling loops is something done externally to the machine. The only way it could be handled internally to the machine is with loops. So that's self defeating. A true Turing machine would be able to run the following code

i=1;
while(i>0){
  i=2-i;
}

Unroll that!
[doublepost=1569603291][/doublepost]

Nitpicking on this is just nitpicking,

Are you saying that there is something wrong with being precise in our word usage when discussing definitions? I would suggest that this is only because the definition you would like to believe in only works if you are sloppy to the point of negligence with your terms.

How many legs does a dog have if you call his tail a leg? Four. Saying that a tail is a leg doesn't make it a leg.

Melted ice isn't ice. Unrolled loops aren't loops.

 

[Norway]

Unroll that!

That's easy. But I don't think you understand the important difference between unbounded and infinite.

Nothing is infinite. Your loop is not infinite.

A Turing machine is not infinite. It's unbounded.
Bitcoin is not infinite. It's unbounded.

 

[cypherblock]

Unroll that!

You can can't loop forever. You can create a finite script that does that operation many time

i=1; while(i>0){ i=2-i; }

Well the value of i doesn't change there. So not that much fun. We can make it calculate the result a 100 times but not infinitely.

Anyway yeah can't loop infinitely in practice. I think the argument is more of an academic one not a practical one. You can say for example (read this somewhere recently) Java is not Turing complete because when you run it the memory is not infinite, and you can run out. So instead you can say the Java language is Turing complete, since when we just evaluate it on that level there is no memory restriction.

With bitcoin script, you can have many repeated code sections that replicate a kind of behavior seen in a loop (instead of executing same exact section of code, execute same exact code written in more than one place), but either you have to know the loop limit in advance, or you have to have repeated sections continuing on forever (where they either execute or just are skipped over based on whether you finished the loop). In fact because of this 'skipping' over essentially infinite sections, you can't have anything that comes after, since the script executer still has to execute each "OP_IF" to see if a code section will execute.

Whether this meets a formal definition of Turing complete or not, well you guys or some mathematicians can debate that (since looping is not the only requirement anyway). It would clearly be an awkward language to do complex work with. A basic "iteration" 1000 times, it can do.

This is why attempting to build a turing machine with bitcoin script is more compelling to me. Probably while trying that you'll find either it is easy or you'll be scratching your head for days. If no one on the internet can do it (let's start a contest?), that might be at least circumstantial evidence it can't be done.

 

[Richy_T]

Yes. What we consider computers are definitely *not* Turing complete (we typically just consider it a close enough model for most reasonable purposes). Fortunately, those are not under discussion here, Bitcoin is. While it certainly has some computational properties and for some specific niche applications, it can be made to ape a Turing machine somewhat, it simply isn't Turing complete or even close enough for government work, let alone jazz.

WRT some of the other stuff, bear in mind that Bitcoin isn't an abstract language definition such as your suggested Java implementation (I have no idea if Java is considered Turing complete. The spec may place limitations), Bitcoin is a concrete implementation (the code is the spec) and is thus inherently limited by the system it operates within. So there's that too, even beyond unrolling potentially infinite loops.

An interesting question, outside of this discussion but with relevance to it is, could we make Bitcoin Turing complete and if so, would we want to? I think freetrader has already addressed that by suggesting that infinite loops would be undesirable. We could possibly do something like Ethereum's gas but I suspect that just becomes a backdoor way of removing Turing completeness (again, I call back to the halting problem which Turing machines have and systems which complete in a finite time do not).

 

[Norway]

https://www.reddit.com/r/btc/comments/da3okt/a_1389_mb_block_was_just_mined_on_bitcoin_cash/

Jake thinks a 1.3MB block is news. A previous bigblocker who had the first brick & mortar bitcoin operation in China. What happened to all these people?

 

[cypherdoc]

bwahaha

 

[cypherdoc]

so sad. protocol devs continue to be mired in complexity:

https://lists.linuxfoundation.org/pipermail/lightning-dev/2019-September/002174.html
[doublepost=1569640027][/doublepost]now this is real progress:

 

[trinoxol]

@cypherblock If somebody were to pay me for it, I can deliver a Turing machine in Bitcoin script. Arbitrary state transition table. Of course, it would have an arbitrary but pre-determined number of steps. It can halt early, though, by transitioning to an end state that loops to itself.

 

[freetrader]

Someone please let Dr Roy Murphy (and his future victims) know that storing his Bitconnect 2.0 SQL databases on BSV will not make Bitconnect 2.0 into a blockchain.

But congrats for being the preferred data archival chain for scammers. A deserved WIN.

 

[lunar]

so sad. protocol devs continue to be mired in complexity:

https://lists.linuxfoundation.org/pipermail/lightning-dev/2019-September/002174.html

"A lightning node accepting a channel must check that the funding transaction
output does indeed open the channel proposed. Otherwise an attacker can claim
to open a channel but either not pay to the peer, or not pay the full amount.
Once that transaction reaches the minimum depth, it can spend funds from the
channel. The victim will only notice when it tries to close the channel and none
of the commitment or mutual close transactions it has are valid."

 

[cypherblock]

WRT some of the other stuff, bear in mind that Bitcoin isn't an abstract language definition such as your suggested Java implementation

Yeah was mostly thinking about the actual script engine part. I mean if you could take bitcoin script engine and script language by themselves, take away all size limits, (maybe add some command that actually outputs something) then you get closer to a general programming language even if it is extremely awkward and limited.

As it is, Bitcoin protocol/implementation, it is almost pointless to talk about turing completeness because of the lack of its ability to do anything except decide if some inputs combined with some previous outputs leave a value of greater than 0 on the stack when run through the script engine. So even if you can compute pi to the 10th decimal place and leave that on the stack, it is challenging to actually make use of that.

 

[Norway]

The point of talking about the Turing completeness in bitcoin is because dr. Craig Wright was the first to point out this property of the system.
[doublepost=1569764534][/doublepost]

- It's not important. (Which it is, in the matter of giving Craig Wright the respect for his insights into bitcoin's inner workings that he deserves.)

You continuously try to downplay this fact and hide your agenda behind a technical facade @cypherblock. But it's easy to see through.

 

[trinoxol]

https://support.kraken.com/hc/en-us/articles/360029029592-Delisting-of-Bitcoin-SV-BSV-April-2019

Kraken takes a 10% fee for any BSV that was not withdrawn at the deadline. This is far above their cost to make the conversion to BTC. If you are willing to treat customers like that it shows ill will towards to currency. It's not a rational business decision. It's a punishment.