Skip to content

Instantly share code, notes, and snippets.

@mgritter
Created August 24, 2020 01:23
Show Gist options
  • Select an option

  • Save mgritter/15c8eef8bdcb0dfbe900c8057a74a079 to your computer and use it in GitHub Desktop.

Select an option

Save mgritter/15c8eef8bdcb0dfbe900c8057a74a079 to your computer and use it in GitHub Desktop.
Soffit grammar implementing the Busy-Beaver Turing machine with four states and tape symbols 0/1.
{
"E->TAPE; E[end];\nH[head]; H->TAPE": "NE[end]; NE->E->TAPE;\nE->ZERO; ZERO[0];\nH[head]; H->TAPE;",
"E<-TAPE; E[end];\nH[head]; H->TAPE": "NE[end]; NE<-E<-TAPE;\nE->ZERO; ZERO[0];\nH[head]; H->TAPE;",
"HEAD[head]; STATE[a]; HEAD->STATE [state];\nHEAD->TAPE; TAPE->VAL; VAL[0];\nTAPE->RIGHT;": "HEAD[head]; STATE[b]; HEAD->STATE [state];\nHEAD->RIGHT; TAPE->VAL; VAL[1];\nTAPE->RIGHT;",
"HEAD[head]; STATE[a]; HEAD->STATE [state];\nHEAD->TAPE; TAPE->VAL; VAL[1];\nLEFT->TAPE;": "HEAD[head]; STATE[b]; HEAD->STATE [state];\nHEAD->LEFT; TAPE->VAL; VAL[1];\nLEFT->TAPE;",
"STATE[b]; VAL[0];\nHEAD[head]; HEAD->STATE [state];\nHEAD->TAPE; TAPE->VAL; LEFT->TAPE;": "VAL[1]; HEAD->LEFT; STATE[a];\nHEAD[head]; HEAD->STATE [state];\nTAPE->VAL; LEFT->TAPE;",
"STATE[b]; VAL[1];\nHEAD[head]; HEAD->STATE [state];\nHEAD->TAPE; TAPE->VAL; LEFT->TAPE;": "VAL[0]; HEAD->LEFT; STATE[c];\nHEAD[head]; HEAD->STATE [state];\nTAPE->VAL; LEFT->TAPE;",
"STATE[c]; VAL[0];\nHEAD[head]; HEAD->STATE [state];\nHEAD->TAPE; TAPE->VAL; TAPE->RIGHT;": "VAL[1]; HEAD->RIGHT; STATE[h];\nHEAD[head]; HEAD->STATE [state];\nTAPE->VAL; RIGHT->TAPE;",
"STATE[c]; VAL[1];\nHEAD[head]; HEAD->STATE [state];\nHEAD->TAPE; TAPE->VAL; LEFT->TAPE;": "STATE[d]; VAL[1];\nHEAD[head]; HEAD->STATE [state];\nHEAD->LEFT; TAPE->VAL; LEFT->TAPE;",
"STATE[d]; VAL[0];\nHEAD[head]; HEAD->STATE [state];\nHEAD->TAPE; TAPE->VAL; TAPE->RIGHT;": "STATE[d]; VAL[1];\nHEAD[head]; HEAD->STATE [state];\nHEAD->RIGHT; TAPE->VAL; TAPE->RIGHT;",
"STATE[d]; VAL[1];\nHEAD[head]; HEAD->STATE [state];\nHEAD->TAPE; TAPE->VAL; TAPE->RIGHT;": "STATE[a]; VAL[0];\nHEAD[head]; HEAD->STATE [state];\nHEAD->RIGHT; TAPE->VAL; TAPE->RIGHT;",
"version": "0.1",
"start": "LEFT->BLANK->RIGHT;\nLEFT[end]; RIGHT[end];\nBLANK->ZERO;\nZERO[0];\nHEAD[head];\nHEAD->BLANK;\nHEAD->A [state];\nA[a];"
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment