<p>Here's a proof that the language is not Turing-complete: its Halting problem can be solved for all programs in your language. This language contains only single loops in sequence, and each loop consists of a finite number of numeric changes to the tape contents. I will gloss over the fact that BF is an 8-bit language, and grant you that the tape contents are all numbers $z \in \mathbb{Z}$. Let $(\alpha_k, \beta_k) \in \mathbb{Z}^{2}$ denote the interval of the tape walked on in statement #k, and let $\nabla_k \in \mathbb{Z}$ denote the amount the tape head moves during each iteration of statement #k. For example, for statment &lt;+>>->+\n, $(\alpha_k, \beta_k) = (-1,3)$ because it moves one item to the left and 2 to the right, plus 1 for the position on which it started, and the net position change is $\nabla_k = 2$. Now, every statement can only increase and decrease its surrounding tape with some vector $v_k \in \mathbb{Z}^{\beta_k-\alpha_k}$, so the program reduces to following simple code:</p>

<p>Input: Infinite tape of zeros, except for a sequence $x$ of numbers starting at position 1</p>

<p>p = 1; // initial tape position</p>

<p>for k = 1..n {</p>

<p>$\quad$while (Tape[p] != 0) {</p>

<p>$\quad\quad$Tape[$p - \alpha_k$ : $p + \beta_k-1$] += $v_k$;</p>

<p>$\quad\quad$p += $\nabla_k$;</p>

<p>$\quad$}</p>

<p>}</p>

<p>Of particular interest is $v_{k,\nabla_k}$ and $v_{k, 2\nabla_k}$ and so forth, because they are the amount the machine will change the items it will inspect next. Now it is easy to solve the Halting problem for any program in your language. Suppose we are have arrived at statement #k and have tape contents Tape, with the tape head at $p$. If $\nabla_k$ = 0, then the head does not move in this loop, and we need only check whether T[$p$] - $m \times v_{k,-\alpha_k} = 0$ for some integer m. If $\nabla_k \not= 0$, then the machine will move across the tape at constant speed. Two things can happen: Tape[$p$] can become zero before the tape head reaches the end of the thus-far written tape - which can be checked in finite time - or it moves past the end of the tape into the unwritten region, at which point it <em>must</em> start repeating itself, which can also be checked in finite time (note that this must be on the positive side of the tape, with $p&gt;0$, otherwise the head has fallen off the tape. It is possible to consider a two-way infinite tape for your language, but the argument still holds). It must start repeating itself in the sense that the contents in Tape[$p - \alpha_k$ : $p + \beta_k$ - 1] must be equal to that of the pervious iteration of loop #k. This is because once arrived in the unwritten region, Tape[$p + \beta_k$] = $v_{k, \beta_k}$, and Tape[$p + \beta_k - \nabla_k] = v_{k,\beta_k} + v_{k, \beta_k - \nabla_k}$, and so forth.</p>

<p>Solving this problem for all statements in a program decides whether that program halts. It is an interesting language nonetheless, and I wonder whether there are programs which have worst-case running times of $\Omega(|x|^2)$, although probably not, and where in the complexity landscape lies the set of languages decided by programs in this BF variant.</p>

CC BY-SA 3.0
2015-10-01T00:21:24.880Z
2015-10-01T00:21:24.880Z
Lieuwe Vinkhuijzen
<p>Consider a language like Brainfuck but without the brackets. At the end of each line (i.e. when "\n" occurs), if the current cell is not 0, then the line is re-executed.</p>

<p>An example of an infinite loop:</p>

<pre><code>+.
// OUTPUT (numbers represent the corresponding ascii characters)
1
2
3
...
</code></pre>

<p>Now, would this hypothetical language be Turing-complete? I'd say yes but I'm not sure, since there's no such a <code>goto</code> thing at all, only <code>while</code>-like.</p>

CC BY-SA 3.0
2015-09-30T22:00:30.330Z
At first glance it seems equivalent, indeed *BoL <line> EoL*  can be interpreted as *do { <line> } while(*prt)*; **BUT** you cannot nest while loops (this is the main difference with the "[,]" of Brainfuck) and there are no conditional instructions that can be used inside the line, so I think it is NOT Turing complete (though making a formal proof of its decidability is probably not so easy).
Marzio De Biasi
CC BY-SA 3.0
2015-10-01T23:17:59.227Z
Please see [tour] and [help/on-topic] for information about the scope of [cstheory.se].
Kaveh
CC BY-SA 3.0
2015-10-02T15:52:11.517Z
similar question [does a do-while loop suffice for TM completeness](http://cs.stackexchange.com/questions/47603/does-a-do-while-loop-suffice-for-turing-completeness) / [cs.se]
vzn
<pl.programming-languages><universal-turing-machines>
Is my language Turing-complete?
Filippo Costa
# Is my language Turing-complete?

(Asked by: username_0 on 2015-09-30)

Consider a language like Brainfuck but without the brackets. At the end of each line (i.e. when "\n" occurs), if the current cell is not 0, then the line is re-executed.
An example of an infinite loop:
+.
// OUTPUT (numbers represent the corresponding ascii characters)
1
2
3
...

Now, would this hypothetical language be Turing-complete? I'd say yes but I'm not sure, since there's no such a goto thing at all, only while-like.

**Tags:** pl.programming-languages, universal-turing-machines

> **Comments:**
> **username_1**: At first glance it seems equivalent, indeed *BoL <line> EoL*  can be interpreted as *do { <line> } while(*prt)*; **BUT** you cannot nest while loops (this is the main difference with the "[,]" of Brainfuck) and there are no conditional instructions that can be used inside the line, so I think it is NOT Turing complete (though making a formal proof of its decidability is probably not so easy).  
> **username_2**: Please see [tour] and [help/on-topic] for information about the scope of [cstheory.se].  
> **username_3**: similar question [does a do-while loop suffice for TM completeness](http://cs.stackexchange.com/questions/47603/does-a-do-while-loop-suffice-for-turing-completeness) / [cs.se]  

---

## 1 answers

### Answer by username_4 on 2015-10-01. Score: 3 | Accepted answer

Here's a proof that the language is not Turing-complete: its Halting problem can be solved for all programs in your language. This language contains only single loops in sequence, and each loop consists of a finite number of numeric changes to the tape contents. I will gloss over the fact that BF is an 8-bit language, and grant you that the tape contents are all numbers $z \in \mathbb{Z}$. Let $(\alpha\_k, \beta\_k) \in \mathbb{Z}^{2}$ denote the interval of the tape walked on in statement #k, and let $\nabla\_k \in \mathbb{Z}$ denote the amount the tape head moves during each iteration of statement #k. For example, for statment <+>>->+\n, $(\alpha\_k, \beta\_k) = (-1,3)$ because it moves one item to the left and 2 to the right, plus 1 for the position on which it started, and the net position change is $\nabla\_k = 2$. Now, every statement can only increase and decrease its surrounding tape with some vector $v\_k \in \mathbb{Z}^{\beta\_k-\alpha\_k}$, so the program reduces to following simple code:

Input: Infinite tape of zeros, except for a sequence $x$ of numbers starting at position 1

p = 1; // initial tape position

for k = 1..n {

$\quad$while (Tape[p] != 0) {

$\quad\quad$Tape[$p - \alpha\_k$ : $p + \beta\_k-1$] += $v\_k$;

$\quad\quad$p += $\nabla\_k$;

$\quad$}

}

Of particular interest is $v\_{k,\nabla\_k}$ and $v\_{k, 2\nabla\_k}$ and so forth, because they are the amount the machine will change the items it will inspect next. Now it is easy to solve the Halting problem for any program in your language. Suppose we are have arrived at statement #k and have tape contents Tape, with the tape head at $p$. If $\nabla\_k$ = 0, then the head does not move in this loop, and we need only check whether T[$p$] - $m \times v\_{k,-\alpha\_k} = 0$ for some integer m. If $\nabla\_k \not= 0$, then the machine will move across the tape at constant speed. Two things can happen: Tape[$p$] can become zero before the tape head reaches the end of the thus-far written tape - which can be checked in finite time - or it moves past the end of the tape into the unwritten region, at which point it *must* start repeating itself, which can also be checked in finite time (note that this must be on the positive side of the tape, with $p>0$, otherwise the head has fallen off the tape. It is possible to consider a two-way infinite tape for your language, but the argument still holds). It must start repeating itself in the sense that the contents in Tape[$p - \alpha\_k$ : $p + \beta\_k$ - 1] must be equal to that of the pervious iteration of loop #k. This is because once arrived in the unwritten region, Tape[$p + \beta\_k$] = $v\_{k, \beta\_k}$, and Tape[$p + \beta\_k - \nabla\_k] = v\_{k,\beta\_k} + v\_{k, \beta\_k - \nabla\_k}$, and so forth.

Solving this problem for all statements in a program decides whether that program halts. It is an interesting language nonetheless, and I wonder whether there are programs which have worst-case running times of $\Omega(|x|^2)$, although probably not, and where in the complexity landscape lies the set of languages decided by programs in this BF variant.


---

