Formal models of computation to have the language and tools:

• what is computation?
• what can and cannot be computed?
• what can and cannot be efficiently computed?

Sidebar: proof

Goal

• basic principles of the theory of computation
• formalize and prove properties of computation
• apply basic principles of computational thinking such as reductions
• exposure to different areas of theory

Questions for Omer

Questions for Omer

Content

Finite Automata

this is a very simple model of computation (a constant amount of memory), meaning we can:

Assuming the Church-Turing thesis holds, there are problems that no computing device can solve.

We can prove this using a counting argument: there are no surjective function from the set of all Turing Machines to the set of all languages over \(\qty {0,1}\).

That is: every mapping from \(TM\) to languages fails to cover some language.

proof

Suppose for contradiction all languages are recognizable, then for all \(L\), there is as truing machine \(M\) recognizing \(L\). Meaning, there’s some surjection \(R: TM \to L\).

thermoregulation is the brain’s regulation of body temperature to respond to heat, cold events.

Studies indicate that cold exposure cold exposure can activate AgRP (stimulate food intake) as a means for the brain leveraging CNS regulation to which would lower the glucose level and maintain glucose homeostatis.

However, cold exposure also trigger energy expenditure, and seems contradictory but not really why?.

The theta/alpha ratio is the ratio between two oscillations measurable by an EEG that is shown to be a possible indicator for AD development.