Countable/Turing-completeness proof

← Back to Countable

This proves Countable's Turing-completeness by implementing Bitwise Cyclic Tag.

Specification

* end of data (first unused accumulator)
* program length
* program length sub 1
* program length sub 2

* program
* carryover 1
* carryover 2
* queue
* queue length
* next queue length
* did increase
* did decrease

if program bit 1 {
  next queue length + queue length
  if queue bit 1 {
    next queue length + 1
    did increase + 1
  }
  carryover 1 + program bit 1
  program + 1
  carryover 2 + program bit 2
  program + 2
  for program length sub 2 {
    next accumulator + program bit n
    end of data + 1
    program + 1
  }
  next accumulator + carryover 1
  end of data + 1
  next accumulator + carryover 2
  end of data + 1
} else {
  did decrease + 1 (from sub algorithm)
  next queue length = queue length - 1 (via sub algorithm)
  carryover 1 + program bit 1
  program + 1
  for program length sub 1 {
    next accumulator + program bit n
    end of data + 1
    program + 1
  }
  next accumulator + carryover 1
  end of data + 1
}
end of data + 2 // skip carryovers
if did decrease {
  queue + 1
  for next queue length {
    next accumulator + queue bit n
    end of data + 1
    queue bit n + 48 // make printable
    print queue bit n
    queue + 1
  }
} else {
  for queue length {
    next accumulator + queue bit n
    end of data + 1
    queue bit n + 48 // make printable
    print queue bit n
    queue + 1
  }
  if did increase {
    next accumulator + carryover 2
    end of data + 1
    carryover 2 + 48 // make printable
    print carryover 2
  }
}
next accumulator + next queue length
end of data + 4 // skip rest
program + 6
program + queue length
queue + 6
queue + program length
carryover 1 + 6
carryover 1 + program length
carryover 1 + queue length
carryover 2 + 6
carryover 2 + program length
carryover 2 + queue length
queue length + 6
queue length + program length
queue length + next queue length
did increase + 6
did increase + program length
did increase + next queue length
did decrease + 6
did decrease + program length
did decrease + next queue length
next queue length + next queue length
next queue length + 6
next queue length + program length
if queue length { print newline } else { break }

Code

This will use the first example provided on BCT's page.

0+26 // end of data
1+5  // program length
2+4  // program length sub 1
3+3  // program length sub 2

4+12  // program pointer
5+17  // carryover 1 pointer
6+18  // carryover 2 pointer
7+19  // queue pointer
8+22  // queue length pointer
9+23  // next queue length pointer
10+24 // did increase pointer
11+25 // did decrease pointer

12+0 13+0 14+1 15+1 16+1 // program (00111)
19+1 20+0 21+1           // queue   (101)
22+3                     // queue length

0*∞<
  1*1<
    *aa4<
      a9+aa8
      *aa7<
        a9+1
        a10+1
      >
      a5+aa4
      4+1
      a6+aa4
      4+1
      *a3<
        a0+aa4
        0+1
        4+1
      >
      a0+aa5
      0+1
      a0+aa6
      0+1
      1&
    >
    2*aa8<
      *aa11<
        a9+1
        2&
      >
      a11+1
    >
    a5+aa4
    4+1
    *a2<
      a0+aa4
      0+1
      4+1
    >
    a0+aa5
    0+1
  >
  0+2
  3*1<
    *aa11<
      7+1
      *aa9<
        a0+aa7
        a7+48
        %aa7
        0+1
        7+1
      >
      3&
    >
    *aa8<
      a0+aa7
      a7+48
      %aa7
      0+1
      7+1
    >
    *aa10<
      a0+aa6
      a6+48
      %aa6
      0+1
    >
  >
  a0+aa9
  0+4
  4+6
  4+aa8
  7+6
  7+a1
  5+6
  5+a1
  5+aa8
  6+6
  6+a1
  6+aa8
  8+6
  8+a1
  8+aa9
  10+6
  10+a1
  10+aa9
  11+6
  11+a1
  11+aa9
  9+aa9
  9+6
  9+a1
  4*1<
    *aa8<
      %10
      4&
    >
    0&
  >
>