##### Introduction

In the previous post we have seen that the halting problem cannot be solved. But maybe the problem is just in our programming languages, so let’s see if we can improve them to disallow non-halting programs.

##### Bounded C

A program can fail to halt by two reasons (we are ignoring I/O, limited memory sizes and all that earthly issues 😀 ): it can get trapped in an infinite loop or we can enter an infinite recursion. So let’s take a language like C and remove these “troublesome” features from it by

- only allowing iteration via the
**for (b = 0; b < a; b++)**construct and - removing the possibility of doing either direct or indirect recursion.

At first sight we haven’t lost a lot. For example we can easily raise numbers to a power

int my_pow(int base, int exp) { int p = 1, i; for (i = 0; i < exp; i++) p *= base; return p; }

or compute the elements of the Fibonacci series.

int fib(int n) { int a = 0, b = 1, i, t; for (i = 0; i < n; i++) { t = a + b; a = b; b = t; } return a; }

But maybe we have lost something subtler…

##### Challenge

Can we make a function in “normal C” that cannot be implemented in our “bounded C”? The answer will be given in the following post… or in the comments 😀

Interesting question 🙂

At first, my guts said “no, there must be something that cannot be implemented without recursion or an unbound loop (a `while` loop)”… but then I started doubting. Let’s see…

If we have a looping algorithm with a complicated break condition that we might put in a `while` loop, but that algorithm has some calculable upper bound in complexity, we might translate:

into…

For example, this can be done with a quicksort: http://jsbin.com/oniruf/4/edit#javascript to http://jsbin.com/oniruf/5/edit#javascript (coded in JS because I suck at C xD).

But, what about algorithms on graph-like data structures? Yeah, every sane algorithm will have an upper-bound depending on the size of the input, but, how do we calculate that size to begin with? Even with the most simple linked-list:

How can that be transformed into de “for (b = 0; b < a; b++)" iterative form? One could argue that a list will never be greater than 1 << sizeof(void*), so the while while loop could be transformed into a for loop with that limit, but that sounds as cheating to me. I can't see how this kind of algorithm can be implemented in Bounded C.

If linked lists wont do it, I'm sure Bounded C cannot implement Bogosort =D. But then again, I have no idea if Bogosort is proven to be non-halting hehe. In fact, I have not much of an idea of what makes a language "Turing complete", but I would bet Bounded C is not =D. It wouldn't even be able to prove Collatz conjecture for a given number!

So, in summary, I would say that no, Bounded C cannot implement everything that normal C can.

BTW, is it possible to preview the formated comment, or use a pretty markup language, like Markdown, to comment here? It was quite annoying to write that comment without knowing how it was gonna look like.

No, because of “security reasons” AKA stupidity. It’s one of the biggest reasons to go back to Blogger, in fact, but, for the moment, I like other features of WordPress too much to go back.

No, and I’ve come to really like the StackExchange interface with its live post preview including Markdown and LaTeX support. You can use “allowed” HTML tags here, to get things like

bold text,emphasized textor`fixed font text`

.Now that I have vented my anger against WordPress, I will comment about your technical comment at lunchtime. 😀

Yep, this is cheating. 😀 The idea is to assume unbounded memory, because otherwise we would be working in a finite state machine (for example, any 64-bit computer is a FSM with no more than states).

This is not a very strong objection, because you can easily modify the list ADT to keep track of the number of elements it contains with ~O(1) cost per operation.

Well, it depends of the type of bogosort. If you are using a “real RNG” you are going outside of the functionality of a normal abstract computer and you need to add a random oracle (it’s like adding extension cards to a PC, though there are much more powerful extensions available). On the other hand, if you are using a PRNG, it can be either guaranteed to halt in time or guaranteed to loop forever, depending on the details of the PRNG and the shuffle algorithm.

You wouldn’t lose that bet 😀

That’s a stronger objection. But notice that the fact that we are unable to bound the growth of the Collatz sequence is contingent in our current knowledge.

So you have proved an important thing: there are important problems that we

don’t know how to encodein Bounded C. But we still don’t know if there are problems thatcannot be encodedin Bounded C…Thanks for your detailed comment!

Ok, fair enough. The solution could be designed differently to fix Bounded C, but the answer to your original question,

“Can we make a function in “normal C” that cannot be implemented in our “bounded C”?would be no, as the function that returns the length of a given linked list, giventhatimplementation of a linked list, would not be implementable in Bounded C. Also, I really like the simplicity and natural “recursivness” of those functional-like lists structures, so adding anything unnecessary to them just feels so wrong to me hehe.Yes! I

knew suspectedit 😛Of course; mine were only gut feelings and random observations, not any attempt to a general proof hehe.

Thanks for the link on the oracle machines; there’s some pretty funky stuff in the computational complexity field it seems.

Dammit! I should have replied to your response. And I thought wp.com supperted BBCode-kinda quotes. What should I have used instead? <blockquote>, <q>?

* Really needs a preview feature, or a more WYSIWYG editor *

Ok, I should have escaped those hehe.

It only supports “some” HTML… For quoting, I use

`<blockquote>`

.I edited your comments above.