The First 37 Branches of Computer Science Generated by CBL

[Charlie-Boo]

English:
PL = Programming Language = Base of Computing = Base
UTM = Universal Turing Machine (concept) = Program/Wff that
outputs/represents the base.
Quine = Program that outputs itself.

CBL 101:
M # P / Q : P = Q(M) : M represents P in base Q
P / Q : There exists an M such that M # P / Q
- W : W is not true.
I = J = Input
x = y = output
YES(a,b) : "Program a halts yes on input b."
# * = 7 recognized branches of Computer Science in 2006 [8, 13, 16, 20,
22, 31, 37]

# WFF is
1 I # I / I Is the UTM a Quine?
2 I # I / J Is this a Quine in that PL?
3 I # I / x In which PL is this a Quine?
4 I # I / YES Is this a Quine?
5 I # J / I Does the UTM in this base output a given value?
6 I # J / J Is this a UTM in that base?
7 I # J / x List all PL in which this outputs that.
8* I # J / YES Program Debugging: Does this program output that?
9 I # x / I List the output of this PL run on its name.
10 I # x / J What does a given program in a certain PL output?
11 I # x / x List all PL in which this is a UTM.
12 I # x / y Get the output of this program run in all PL.
13* I # x / YES Program Analysis: What does this program output?
14 x # I / I List the UTM of this base.
15 x # I / J What programs output this in that base?
16* x # I / YES Program Synthesis: What programs output this?
17 x # x / I List the Quines in this base.
18 x # x / x List all UTMs that are Quines.
19 x # x / y List all Quines in all PL.
20* x # x / YES Recursion Theory: List all Quines.
21 x # y / y List all UTM in all PL.
22* x # y / z PL Semantics: List the Programs and their outputs for
all PL.
23 x # y / YES TM Semantics: List all TM and their output.
24 I / I Does this base have a UTM?
25 I / J Is this representable in that base?
26 I / x In what bases is this representable?
27 I / YES Is this r.e.?
28 x / I What is representable in this base?
29 x / x List the bases that represent themselves.
30 x / y List all bases and everything they represent.
31* x / YES Positive Theory of Computation: What is r.e.?
32 - I / x List all bases that cannot represent this.
33 - I / YES Is this not r.e.?
34 - x / I List what is not representable in this base.
35 - x / x List all bases that have no UTM.
36 - x / y List all bases and what they cannot represent.
37* - x / YES Theory of Computation: List all non-r.e. sets.

C-B