The unfortunately (but aptly) named brainf*ck is my favorite esoteric programming language. The whole language has only 8 commands, yet is Turing equivalent, meaning it has the same computational power as a Turing machine. As amazing as it sounds, this means any computable function can be computed with a BF program! A simple way to prove that a language is Turing complete is to use it to implement another which already has been proven Turing complete. Due to its simplicitly, BF lends itself well to this task.
So, here is a simple BF interpreter written in EMC's RS274 dialect:
(print, PROGRAM START)
o100 while [##<_pc> ne 0]
#1 = ##<_pc>
o101 if [#1 eq 1] (memory increment)
##<_p> = [##<_p> + 1]
o101 endif
o102 if [#1 eq 2] (memory decrement)
##<_p> = [##<_p> - 1]
o102 endif
o103 if [#1 eq 3] (pointer increment)
#<_p> = [#<_p> + 1]
o103 endif
o104 if [#1 eq 4] (pointer decrement)
#<_p> = [#<_p> - 1]
o104 endif
o105 if [#1 eq 5] (loop start)
##<_sp> = #<_pc>
#<_sp> = [#<_sp> + 1]
o105 endif
o106 if [#1 eq 6] (loop end conditional)
#<_sp> = [#<_sp> - 1]
o1060 if [##<_p> ne 0]
#<_pc> = [##<_sp>-1]
o1060 endif
o106 endif
o107 if [#1 eq 7] (print value)
#3 = ##<_p>
(print, ASCII: #3)
o107 endif
g0 x1
#<_pc> = [#<_pc> + 1]
o100 endwhile
(print, PROGRAM END)
This interpreter doesn't support the input command (but that isn't needed for Turing completeness anyway) and just prints out the output in numeric format. This is pretty boring, so I added a set of functions for carving out letters. See the complete source code.
I came here through a web search wondering whether G-code was Turing-complete. Thanks for making my day by proving that in the way you did.
ReplyDeleteI now feel the urge to make parts using BF code.
This comment has been removed by the author.
ReplyDelete