Skip to content

wenkokke/cgtm

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

15 Commits
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

CG Turing Machines

Build Status

This is a small library which generates VISL CG-3 code from Turing machine specifications, proving that VISL CG-31 is Turing-complete2. This development is accompanied by a blog post, VISL CG-3 is the new assembler.


[1]: More specifically, the subset which only uses a single SECTION, ADDCOHORT and REMCOHORT. While it also uses the ADD command, this could be simulated by adding "<Tag>" cohorts. However, for reasons of clarity, I've not done this.

[2]: The other direction—the fact that VISL CG-3 grammars can be run on a Turing machine—is probably adequately proven by the VISL CG-3 implementation.