SU-CS242 SEP242024
Last edited: August 8, 2025“the ways in which one can dividing the original program together depends on the way people can glue problems together. one must provide new kinds of glue in teh programming language”
Goals of PL
balancing between:
- productivity—Python
- safety—Coq, Lean
- performance—C,
Edges:
- safety+performance—Rust (not really productive)
- productivity+safety—ML, Maskell (not very performant)
- productivity+performance—Matlab (not very safe)
Java and C++ tries to do all three, but makes them more contradictory systems because you can’t get optimality on all three
SU-CS242 SEP262024
Last edited: August 8, 2025MAIN IDEA: Combinator Calculus
primitive recursion vs general recursion
primitive recursion is a form of recursion whereby you don’t get to modify the amount of recursion after the loop is defined. general recursion have control flow.
non-termination
all forms of general recursion either
rewrite system
- \(\to\) is a single rewrite
- \(\to^{*}\) stands for the reflexive, transitive closure of \(\to\) (i.e. zero or more rewrites—“we skipped the middle”)
SU-CS254 FEB032025
Last edited: August 8, 2025Key question: why is having a SAT oracle less powerful than \(\text{SAT} \in P\)? What’s the role of a oracle?
with a SAT oracle…
We can solve NP problems because SAT is NP complete; we can solve coNP problems we can now finally just negate it.
polynomial hierarchy collapses if \(\text{SAT} \in \text{P}\)
We can solve \(\Sigma_{j}\) because we can peel off inner languages; for instance, for \(\Sigma_{2}\):
\begin{equation} x \in L \Leftrightarrow \exists w_{1} \forall w_{2} V\qty(x, w_{1}, w_{2}) = 1 \end{equation}
SU-CS254 FEB052025
Last edited: August 8, 2025Key Sequence
Notation
New Concepts
- randomness
- some random algorithms
- randomized turing machine