Do we need to live with the uncertainty?

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 😀

Advertisements

8 thoughts on “Do we need to live with the uncertainty?

  1. Demian says:

    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:

    while (some_condition()) { ... }
    

    into…

    for (size_t i = 0, l = max_iterations(); i < l; i++) {
        if (!some_condition()) break;
        ...
    }
    

    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:

    size_t list_length(list_t* list) {
        return list ? 1 + list_length(list->next) : 0;
    }
    // or, iteratively...
    size_t list_length(list_t* list) {
        size_t len = 0;
        while (list) {
            list = list->next;
            len++;
        }
        return len;
    }
    

    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.

    • Demian says:

      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.

      • mchouza says:

        BTW, is it possible to preview the formated comment

        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.

        or use a pretty markup language, like Markdown, to comment here?

        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 text or fixed font text.

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

    • mchouza says:

      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.

      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 2^{2^{64}} states).

      I can’t see how this kind of algorithm can be implemented in Bounded C.

      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.

      I have no idea if Bogosort is proven to be non-halting

      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 O(n!) or guaranteed to loop forever, depending on the details of the PRNG and the shuffle algorithm.

      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

      You wouldn’t lose that bet 😀

      It wouldn’t even be able to prove Collatz conjecture for a given number!

      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 encode in Bounded C. But we still don’t know if there are problems that cannot be encoded in Bounded C…

      Thanks for your detailed comment!

  2. Demian says:

    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.

    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, given that implementation 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.

    You wouldn’t lose that bet 😀

    Yes! I knew suspected it 😛

    But we still don’t know if there are problems that cannot be encoded in Bounded C…

    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.

    • Demian says:

      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 *

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s