<p>No, the alt-stack doesn't make bitcoin script a Turing-complete language.</p>

<p>While script has two stacks, in order to simulate a two-stack pushdown automata (which is Turing complete), one has to be able to implement a finite-state control unit. This cannot be done in bitcoin script, since there is no looping or conditional branching available. It is possible to write a script that goes through the motions of running a Turing machine program by unrolling loops, but that will only work for a machine and input combination that terminates. It is very simple to write a Turing machine with a finite input string that loops indefinitely eg. consider the Turing machine defined by</p>

<p>states: q0 (initial), q1 and q3 (final)</p>

<p>and tape alphabet {0, 1}</p>

<p>where the transitions are</p>

<p>(q0, 0) -> (q1, 0, move left)</p>

<p>(q1, 0) -> (q1, 0, move left)</p>

<p>(q1, 1) -> (q1, 1, move right)</p>

<p>Given input 01, this machine will just loop infinitely, as simulated here:</p>

<p><a href="http://turingmachinesimulator.com/shared/ojvubpsgkm" rel="nofollow noreferrer">http://turingmachinesimulator.com/shared/ojvubpsgkm</a></p>

<p>Attempting to "unroll" this as a bitcoin script will never finish.</p>

CC BY-SA 4.0
2018-07-07T08:14:00.193Z
2018-07-07T08:14:00.193Z
Paul Clarke
<p>You may be interested in <a href="https://paulgeorgiou.org/post/2018/03/making-a-turing-machine-in-bitcoins-script/" rel="nofollow noreferrer">a post I wrote</a>. I wrote a Turing Machine (by utilizing the two stacks) and made a <a href="https://www.blocktrail.com/BTC/tx/22553e36c09bbb5e470826b70f53152d3bbc22666991d92cb423ab128e03aaf8" rel="nofollow noreferrer">test transaction</a>.</p>

<p>Basically if we assume that our program will halt, then it requires only a finite number of instructions, which is supported by the Bitcoin script. Unfortunately the Bitcoin script VM only allows a limited number of operations to be executed so only very short programs can be written in practice.</p>

CC BY-SA 3.0
2018-04-19T09:05:43.130Z
2018-04-19T09:05:43.130Z
veqtrus
<p>Yes but sometimes clarke the bitcoin source of Autoscope interesting, sometimes we need to see the beginning of the first things of the next.</p>

<p>Confirmation of none technical aim can terminate me asking task bitcoin interested layer at low @ understanding per jam dot net.</p>

<p>where the transitions are</p>

<p>(q0, 0) -> (q1, 0, move left)</p>

<p>(q1, 0) -> (q1, 0, move left)</p>

<p>(q1, 1) -> (q1, 1, move right)</p>

<p>Given also input 01
urgent. thanks</p>

CC BY-SA 4.0
2020-05-05T06:11:12.163Z
2020-05-05T06:11:12.163Z
bil80
<p>The wiki documents the presence of an "alt stack" in Script:</p>

<ul>
<li><code>OP_TOALTSTACK</code> Puts the input onto the top of the alt stack. Removes it from the main stack.</li>
<li><code>OP_FROMALTSTACK</code> Puts the input onto the top of the main stack. Removes it from the alt stack.</li>
</ul>

<p>It appears then that Script may qualify as a Two-Stack Pushdown Automaton. And this system is known to be equivalent to a Turing Machine. For example:</p>

<blockquote>
  <p>To see the equivalence, just think of the first stack as the contents of the tape to the left of the current position, and the second as the contents to the right. Start by pushing the normal "bottom of stack" markers on both stacks, then we can simulate the TM by popping from the right stack and pushing to the left to move right, and vice versa to move left. If we hit the bottom of the left stack we behave accordingly (halt and reject, or stay where you, depending on the model), if we hit the bottom of the right stack, we just push a blank symbol onto the left.</p>
</blockquote>

<p><a href="https://cs.stackexchange.com/questions/2832/is-a-push-down-automaton-with-two-stacks-equivalent-to-a-turing-machine/2833#2833">https://cs.stackexchange.com/questions/2832/is-a-push-down-automaton-with-two-stacks-equivalent-to-a-turing-machine/2833#2833</a></p>

<p>Wikipedia defines "Turing complete" as:</p>

<blockquote>
  <p>In computability theory, a system of data-manipulation rules (such as a computer's instruction set, a programming language, or a cellular automaton) is said to be Turing complete or computationally universal if it can be used to simulate any Turing machine.</p>
</blockquote>

<p><a href="https://en.wikipedia.org/wiki/Turing_completeness" rel="noreferrer">https://en.wikipedia.org/wiki/Turing_completeness</a></p>

<p>This thread makes reference to the alt stack, claiming that its presence makes Script Turing complete:</p>

<p><a href="https://www.reddit.com/r/Bitcoin/comments/7yb3is/where_is_the_evidence_that_bitcoin_is_turing/duf1rt9/" rel="noreferrer">https://www.reddit.com/r/Bitcoin/comments/7yb3is/where_is_the_evidence_that_bitcoin_is_turing/duf1rt9/</a></p>

<p>That thread links to this thread, which contains the following:</p>

<blockquote>
  <p>While it is a well known CS result that a two-stack push-down automata has the same power as a Turing Machine, Bitcoin Script cannot operate as a two-stack push-down automata. Even though Bitcoin Script has two stacks, Bitcoin Script doesn't have an associated finite state machine that you can create.</p>
</blockquote>

<p><a href="https://reddit.com/r/btc/comments/6hjxiy/new_craig_wright_interview_part_2_on/diz9g69/?context=3" rel="noreferrer">https://reddit.com/r/btc/comments/6hjxiy/new_craig_wright_interview_part_2_on/diz9g69/?context=3</a></p>

<p>In other words, there may be two stacks, but there's no way to sufficiently power them to create a Turing Machine.</p>

<p>Is Bitcoin Script Turing complete given the presence of the alt stack? If not, what specific functionality is missing?</p>

CC BY-SA 3.0
2018-03-07T19:51:51.913Z
Yes, that makes it as turing-complete as ethereum (or since none of them can implement 'infinite tape' required for TM, either of them aren't?) Deeper question you might want to ask is about the effect of time it takes for script validation.
skang404
<script><turing-completeness>
Does the alternative stack make Script Turing complete?
Rich Apodaca
# Does the alternative stack make Script Turing complete?

(Asked by: username_0 on 2018-03-07)

The wiki documents the presence of an "alt stack" in Script:

* `OP_TOALTSTACK` Puts the input onto the top of the alt stack. Removes it from the main stack.
* `OP_FROMALTSTACK` Puts the input onto the top of the main stack. Removes it from the alt stack.

It appears then that Script may qualify as a Two-Stack Pushdown Automaton. And this system is known to be equivalent to a Turing Machine. For example:

> To see the equivalence, just think of the first stack as the contents of the tape to the left of the current position, and the second as the contents to the right. Start by pushing the normal "bottom of stack" markers on both stacks, then we can simulate the TM by popping from the right stack and pushing to the left to move right, and vice versa to move left. If we hit the bottom of the left stack we behave accordingly (halt and reject, or stay where you, depending on the model), if we hit the bottom of the right stack, we just push a blank symbol onto the left.

<https://cs.stackexchange.com/questions/2832/is-a-push-down-automaton-with-two-stacks-equivalent-to-a-turing-machine/2833#2833>

Wikipedia defines "Turing complete" as:

> In computability theory, a system of data-manipulation rules (such as a computer's instruction set, a programming language, or a cellular automaton) is said to be Turing complete or computationally universal if it can be used to simulate any Turing machine.

<https://en.wikipedia.org/wiki/Turing_completeness>

This thread makes reference to the alt stack, claiming that its presence makes Script Turing complete:

<https://www.reddit.com/r/Bitcoin/comments/7yb3is/where_is_the_evidence_that_bitcoin_is_turing/duf1rt9/>

That thread links to this thread, which contains the following:

> While it is a well known CS result that a two-stack push-down automata has the same power as a Turing Machine, Bitcoin Script cannot operate as a two-stack push-down automata. Even though Bitcoin Script has two stacks, Bitcoin Script doesn't have an associated finite state machine that you can create.

<https://reddit.com/r/btc/comments/6hjxiy/new_craig_wright_interview_part_2_on/diz9g69/?context=3>

In other words, there may be two stacks, but there's no way to sufficiently power them to create a Turing Machine.

Is Bitcoin Script Turing complete given the presence of the alt stack? If not, what specific functionality is missing?

**Tags:** script, turing-completeness

> **Comments:**
> **username_1**: Yes, that makes it as turing-complete as ethereum (or since none of them can implement 'infinite tape' required for TM, either of them aren't?) Deeper question you might want to ask is about the effect of time it takes for script validation.  

---

## 3 answers

### Answer by username_2 on 2018-07-07. Score: 3

No, the alt-stack doesn't make bitcoin script a Turing-complete language.

While script has two stacks, in order to simulate a two-stack pushdown automata (which is Turing complete), one has to be able to implement a finite-state control unit. This cannot be done in bitcoin script, since there is no looping or conditional branching available. It is possible to write a script that goes through the motions of running a Turing machine program by unrolling loops, but that will only work for a machine and input combination that terminates. It is very simple to write a Turing machine with a finite input string that loops indefinitely eg. consider the Turing machine defined by

states: q0 (initial), q1 and q3 (final)

and tape alphabet {0, 1}

where the transitions are

(q0, 0) -> (q1, 0, move left)

(q1, 0) -> (q1, 0, move left)

(q1, 1) -> (q1, 1, move right)

Given input 01, this machine will just loop infinitely, as simulated here:

<http://turingmachinesimulator.com/shared/ojvubpsgkm>

Attempting to "unroll" this as a bitcoin script will never finish.


---

### Answer by username_3 on 2018-04-19. Score: 2

You may be interested in [a post I wrote](https://paulgeorgiou.org/post/2018/03/making-a-turing-machine-in-bitcoins-script/). I wrote a Turing Machine (by utilizing the two stacks) and made a [test transaction](https://www.blocktrail.com/BTC/tx/22553e36c09bbb5e470826b70f53152d3bbc22666991d92cb423ab128e03aaf8).

Basically if we assume that our program will halt, then it requires only a finite number of instructions, which is supported by the Bitcoin script. Unfortunately the Bitcoin script VM only allows a limited number of operations to be executed so only very short programs can be written in practice.


---

### Answer by username_4 on 2020-05-05. Score: -2

Yes but sometimes username_2 the bitcoin source of Autoscope interesting, sometimes we need to see the beginning of the first things of the next.

Confirmation of none technical aim can terminate me asking task bitcoin interested layer at low @ understanding per jam dot net.

where the transitions are

(q0, 0) -> (q1, 0, move left)

(q1, 0) -> (q1, 0, move left)

(q1, 1) -> (q1, 1, move right)

Given also input 01
urgent. thanks


---

