Anything that can be computed by a reasonable model of computation can also be computed by a turing machine.

“Everyone’s intuitive notion of algorithms is a Turing-machine”

Note that this is not a theorem: its just a scientific hypothesis because we have no formalization of the “intuitive notion”.

multi-tape machines

Consider:

would this give us something stronger? as in, we modify our transition function as simultaneously operating on all tapes

A circuit is a new model of computation, like turing machines. circuit are defined in terms of boolean logic, with components \(\text{AND}, \text{OR}, \text{NOT}\).

Most important quirk

constituents

• sequence of \(n\) true/false inputs \(x_1, …, x_{n}\)
• a graph with nodes belled AND/OR/NOT combining these things pairwise boolean gates
• a single output true/false

complexity measures of circuits

size (circuits)

number of gates—corresponds roughly to “time complexity”

depth (circuits)

length of the longest part from the output gate to inputs—roughly “parallel time complexity”

civil rights movement starting

civil rights moment was kicked off by the Rosa Parks incident, which caused the Montomery Bus Boycott.

Martin Luther King capitalized the incident to kick start civil rights movement. He employed the method of nonviolence movement.

educational integration in the civil rights movement

• K-12 disintegration: Brown v. Board of Education
• University of Georgia was the first disintegrated university in the south

service integration in the civil rights movement

Lunch counter boycotts. Nashville became the first desegregated lunch counter.

A part of the New Deal programs for unmarried men to go and build American infrastructure outdoors under reasonably harsh conditions. “Kind of like boy scouts for adults.” It is structured like the military; Black men were segregated and not given leadership roles.

1933-1942.