Hi Neil.

09-Jun-04 13:58:00, Neil Heller wrote to Jasen Betts


 NH> JB>that sounds interesting, but as I understand traversing a list
 NH> with a JB>loop will never end.

 NH> Is that the same as a circular buffer?

a circular buffer could be done using cells linked by pointers but that's
not normally how it's done.

a circular buffer is is usually done using a regular array and with index
counters that loop back to the start when they hit the end.

the keyboard buffer that's maintained by the BIOS is a real life example.
(except it uses pointers instead of index counters, but so would I)

 NH> JB>you seem to have implemented a solution which translates the
 NH> problem JB>into the halting problem. :)

 NH> If there is now a new problem, has the problem been solved?

The halting problem is a paradox invented by Alan Turing.
there is no solution to the halting problem.

The halting problem goes like this given a program listing and it's input
data  develop a program that can determine if the program in the listing
will ever come to the end and halt.

the proof that this is an impossible task goes like this.

assume you have a program capable of solving the halting problem.
modify it so that it goes into an infinite loop if the input is a program
that halts and exits normally otherwise

give this program itself for input. how does it behave?


simple circular buffer: (untested)

#define bufsize 20
#define buftype int

#define NULL_ITEM -3
#define BUFFER_FULL -2
#define BUFFRR_EMPTY -1
#define BUFFER_OK 0

static buftype the_buffer[bufsize]
static int buf_head=0,buf_tail=0;

 /* circular increment for a circular buuffer */
#define bufer_next(n)  ( n < (buffsize -1)? n+1:0 )

int push(const buftype *item){   /* push an item into the buffer */
  int n=buffer_next(buf_head);
  if(n==buf_tail) return BUFFER_FULL;
  if (!item) return NULL_ITEM;
  memcpy( &the_Buffer[buf_head=n],item,sizeof buftype);
  return BUFFER_OK;
  }

int pull(buftype *item) { /* pull the oldest item from the buffer */
  if(buf_tail == buf_head) return BUFFER_EMPTY;
  if (!item) return NULL_ITEM;
  buf_tail=buffer_next(buf_tail);
  memcpy(item, &the_Buffer[buf_tail],sizeof buftype);
  return BUFFER_OK;
  };


 -=> Bye <=-
---