Introduction E9F5FC

Questions FFFFC0

• View
• Edit
• History
• Print

See: Multiplication, Category theory of computability, Arithmetical hierarchy, Yates Index Set Theorem, Lambda calculus

A deterministic finite automaton consists of:

• The set of objects: A finite set of states {$Q$} which includes an initial state {$q_0\in Q$} and a set of accept states {$F\subset Q$}.
• The set of morphisms.
• A word category that consists of a single object, the identity morphism, and a set {$\Sigma$} of the other morphisms, the alphabet, and all of the words generated by concatenating that alphabet.
• A functor that takes the set of morphisms to a set of

The Dyck language (of parentheses) is a deterministic context free language. It's generated by the following production rules, in Greinbach normal form, and how it can be expressed by a pushdown automaton.

• {$Z\rightarrow (A$} Given start tray Z and input "(", push A onto the stack.
• {$A\rightarrow )$} Given tray A and input ")", pop A off the stack.
• {$A\rightarrow (AA$}. Given tray A and input "(", pop A off the stack, and push AA onto the stack.
• Turing machine is the same as a deterministic two-stack machine (a two-stack push down automaton): One stack store the symbols on the tape to the left of the head, and the other stack stores the symbols on the tape to the right of the head. (Hopcroft and Ullman, 7.8 Restricted Turing Machines)
• A two-counter machine (storing two integers) can simulate one stack. Indeed, a two-counter machine can simulate an arbitrary Turing machine.

The following production rules characterize:

• Finite automata {$X\rightarrow aX$}
• Context free grammars / push down automata {$X\rightarrow aXb$} (p.81)
• Context sensitive grammars {$Xcd \rightarrow dXc$} (carries {$c$} across {$d$})
• Turing machines {$X \rightarrow \epsilon $} disappears
• Unrestricted grammars are given by {$\alpha \rightarrow \beta$} where these are unrestricted strings of symbols. Context sensitive grammars are those for which {$|\alpha|\leq|\beta |$}.

Deterministic context free grammars should be those for which the production rules are unique - there is only one production rule for each variable -> input+variable+tray. (But what would it mean for there to be two?) Note that deterministic automaton similarly only allow for one prodution rule for each variable -> input+variable.

Linear bounded Turing machines are those whose external memory (the space where it can write) is only as large as the input. Thus it cannot "think outside the box". These are equivalent to the context sensitive grammars. Note that this means that requiring the produced strings to grow is the same as restricting the memory, thus the restrictions hold in opposite directions. In either case, it forces explicitness. Thus anything sophisticated is forced to be implicit, to destroy knowledge.

Context-free means that in the production rule, on the left hand side, the {$X$} is by itself, without any other symbols, which is to say, without any context.

Pushdown automata are understood to be nondeterministic, by definition. They are deterministic when there is never a choice between reading no input and reading an input, and never a choice in either case. For (nondeterministic) pushdown automata, there is no difference between the languages accepted by the empty stack criterion or the final state criterion. For the deterministic pushdown automata, the empty state accepts only those words which have no prefix that would be accepted.

Joseph Austin at Math Future: I've been thinking that Computing itself can be treated somewhat axiomatically. As I've said before, there is a morphism of some sort between the Field Axioms with exponentiation, Finite Automata, and Structured Programs. For example, the Sequence, Decisions (choice) and Loops (repetition) in programming correspond to the sequence, choice, and repetition structures of regular languages which in turn correspond to product, sum, and power operations in arithmetic.

• There is a qualitative hierarchy of computing devices. And they can be described in terms of matrices.
• Complexity measures for Boolean functions.
• How is a Boolean function similar to a linear functional?
• If we think of a Turing machine's possible paths as a category, what is the functor that takes us to the actual path of execution?

Readings

• W: Automata theory. Hierarchy in terms of powers.
• Reginald Braithwaite. A Brutal Look at Balanced Parentheses, Computing Machines, and Pushdown Automata

• All systems are the same: The Principle of Computational Equivalence [1, 2], due to S. Wolfram, is the heuristic statement that almost all processes (involving classical computations) that are not obviously simple are of equivalent sophistication. My corollary: Simple processes can be considered degenerate, be catalogued, and so on. The classification of these degenerate processes is the dual flip side of the universal nondegenerate system.
• Mathematical structures are all degenerate systems (as with symmetries) which do not express the complexity of a full fledged system, as most systems are.
• Automata are important for the dynamics of the three languages.
• Is every computation system of sufficient sophistication equivalent to a house of knowledge? And are lesser systems equivalent to a part of a house of knowledge?
• Algebraic thinking is step-by-step, as with a PDA, state-by-state.
• What is the relationship between circumstances (12 topologies) and the meaning of context in automata theory.
• Finite automata - truth tables. Push down automata - type theory. Truth tables don't scale, look at negation.
• Simply typed lambda calculus. Can think of the base types as the atomic units "m", "sec", and think of functions sec->m as ratios "m/sec", which can yield very complicated ratios.
• Computational definition of function (lambda calculus) = functional definition of computation (Turing machine)
• Computerphile: Graham Hutton's observation: Y combinator is the expression of recursion in the lambda calculus. It has a dual structure which he thinks is related to the double strandedness of DNA.
• Gauge field = finite automata. Particle = pushdown automata.
• Known that polynomial time is a subset of polynomial space (memory). But not known if polynomial space is a subset of polynomial time.
• Recursion: loop = loop. This is like X = X.
• from my dream: churning by automata

{$\mathbf{Fin}=\{x|W_x \textrm{ is finite}\}$}, {$\mathbf{Rec}=\{x|W_x \textrm{ is recursive}\}$}, {$ \{x:W_x\equiv_T A\} \textrm{ is } \Sigma^A_3\textrm{-complete}$}.

Automata

• Connes noncommutative geometry is based on cyclic permutations where ABC = CAB, and this yields cyclic homology for associative algebras.
• Nondeterministic algorithm can be understood as the allowing of all possiblities, as with the indefinite origin.
• {$\forall D\exists f\forall g(f=g)$} arithmetic hierarchy: derivative
• {$\forall \epsilon \exists \delta \forall x$} arithmetic hierarchy: universality: for all objects there exists a unique morphism
• In deep learning, how does the machine know if it is in training mode or in testing mode? And what does that mean about its self-observing?

Recursive functions

• Stanford Encyclopedia: Recursive Functions

Philosophy of Computer Science

• https://blog.apaonline.org/2021/04/08/the-philosophy-of-computer-science/?amp
• https://freecomputerbooks.com/Philosophy-of-Computer-Science.html
• https://builtin.com/software-engineering-perspectives/cs-philosophy-programs

Computational learning theory

• Michael J. Kearns. An introduction to computational learning theory.
• Shai Ben-David - Machine Learning Course (Computational Learning Theory)
• Andrius: I wonder if there are any connections with the arithmetical hierarchy in computability theory. In that hierarchy, the sigmas and the pis are intermixed. So I wonder if there are any ways that pis (products) get interspersed between the truncation levels?
• Astra: If you have a Pi-type, then the truncatedness level is that of the codomain, so this behavious is a bit different from what you would see in that hierarchy