Statements (27)
| Predicate | Object |
|---|---|
| gptkbp:instanceOf |
theoretical computer science
|
| gptkbp:hasApplication |
demonstrating undecidability
studying minimal universal computation |
| gptkbp:hasComponent |
gptkb:alphabet
production rules deletion number |
| gptkbp:hasProperty |
simplicity
undecidability (for certain cases) |
| gptkbp:hasVariant |
binary tag system
cyclic tag system |
| gptkbp:heldBy |
Turing complete (for certain parameters)
a type of rewriting system a type of string rewriting system |
| https://www.w3.org/2000/01/rdf-schema#label |
Tag Systems
|
| gptkbp:introducedIn |
1920
|
| gptkbp:inventedBy |
gptkb:Emil_Post
|
| gptkbp:relatedTo |
gptkb:Post_canonical_system
Technical Machine cellular automata |
| gptkbp:SIM |
Turing machine (for certain parameters)
|
| gptkbp:studiedIn |
gptkb:complexity_theory
computability theory |
| gptkbp:usedIn |
gptkb:logic
automata theory theory of computation |
| gptkbp:bfsParent |
gptkb:Zwipe
|
| gptkbp:bfsLayer |
7
|