All Questions
Tagged with ho.history-overview big-picture
8 questions
3
votes
2
answers
365
views
What are some "who ordered that?" moments in theoretical computer science?
I was recently listening to Sean Carroll's interview with Scott Aaronson, and the two of them briefly talked about surprises in their respective fields (theoretical and particle physics, and ...
14
votes
1
answer
2k
views
Why was there a need for Martin-Löf to create intuitionistic type theory?
I've been reading up on Intuitionistic Type Theory (ITT) and it does make sense. But what I'm struggling to understand is "why" was it created in the first place?
Intuitionistic Logic (IL) and Simply-...
- 5,385
4
votes
3
answers
693
views
Why is lambda calculus so "function" oriented?
I've always had this question nagging at me subconsciously but have never been able to intuitively grasp it. Why does $\lambda$-calculus have a functional notation? Why is everything a function?
It ...
- 5,385
23
votes
2
answers
2k
views
What was the original intent for the creation of Lambda calculus?
I've read that initially Church proposed the $\lambda$-calculus as part of his Postulates of Logic paper (which is a dense read). But Kleene proved his "system" inconsistent after which, Church ...
- 5,385
28
votes
3
answers
4k
views
Impact of Grothendieck's program on TCS
Grothendieck has passed away. He had massive impact on 20th century mathematics continuing into the 21st century. This question is asked somewhat in the style/spirit, for example, of Alan Turing's ...
- 11.1k
95
votes
7
answers
31k
views
What is the contribution of lambda calculus to the field of theory of computation?
I'm just reading up on lambda calculus to "get to know it". I see it as an alternate form of computation as opposed to the Turing Machine. It's an interesting way of doing things with functions/...
- 5,385
8
votes
2
answers
3k
views
Why were Finite Automata and Turing Machines created?
It seems the creation of Turing Machines and finite automata were apart by at least 2+ decades. That is TMs don't really reference FAs for their working and vice versa; TMs and FAs were developed ...
- 5,385
71
votes
5
answers
7k
views
The origin of the notion of treewidth
My question today is (as usual) a bit silly; but I would request you to kindly consider it.
I wanted to know about the genesis and/or motivation behind the treewidth concept. I sure understand that ...
- 1,983