2
$\begingroup$

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.

$\endgroup$
3
  • 3
    $\begingroup$ 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). $\endgroup$ Sep 30, 2015 at 22:00
  • $\begingroup$ Please see tour and help center for information about the scope of Theoretical Computer Science. $\endgroup$
    – Kaveh
    Oct 1, 2015 at 23:17
  • $\begingroup$ similar question does a do-while loop suffice for TM completeness / Computer Science $\endgroup$
    – vzn
    Oct 2, 2015 at 15:52

1 Answer 1

3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.