New answers tagged lo.logic
1
vote
Turing Machines and Logic
There is a rich field known as descriptive complexity which studies the connection between computability/complexity and logic; I highly recommend checking out Immerman's book or the summary page on ...
- 852
0
votes
Theoretical Computer Science vs other Sciences?
P vs NP is one of the most important questions in mathematics and it is at the heart of TCS.
It has tremendous practical and philosophical implications:
Are all easily checkable theorems also easily ...
- 790
0
votes
Theoretical Computer Science vs other Sciences?
Physicist here. I have three things to contribute to this discussion:
Firstly, the most exciting things happening in theoretical fundamental physics these days are all related to quantum information ...
- 111
1
vote
Theoretical Computer Science vs other Sciences?
It seems that your education has sparked (or noticeably deepened) your fascination for theory in general, a fascination you can experience and build upon in the field of TCS and could experience and ...
- 193
3
votes
Theoretical Computer Science vs other Sciences?
I have worked in IT for 27'ish years, and studied CS in Germany as well; even at a more theoretical uni (there was a separate "technical" uni in our city which got to do all the robotics ...
- 219
2
votes
Theoretical Computer Science vs other Sciences?
Back in college, I loved TCS for the mental gymnastics. I'd argue that, for better or worse, they shaped the way my mind works: I'm a decent programmer and, generally, technologist and I think that's ...
- 121
1
vote
Theoretical Computer Science vs other Sciences?
There is a tension between theory and praxis in any discipline. In TCS, many ideas that are cooked up in labs as products of research and development eventually surface 20 years later in industry. ...
- 111
3
votes
Theoretical Computer Science vs other Sciences?
I recently saw a video of Richard Feynman (the famous physicist), in which he explains a bunch of physical phenomena. It’s on youtube, it‘s a famous one, and it completely blew my mind and it just got ...
- 1,977
8
votes
Theoretical Computer Science vs other Sciences?
My impression from your comments is that perhaps you have just not seen enough theoretical CS to get to some of the kind of content you are excited about in, say, physics.
I'll also point out that you ...
- 36.3k
4
votes
Theoretical Computer Science vs other Sciences?
Maybe I can offer some interesting point of view here:
I finished my Bachelors degree in physics and started a bachelors degree in software engineering afterwards. People often ask me why, which the ...
- 141
11
votes
Theoretical Computer Science vs other Sciences?
I run a small software business producing XML processing tools, so I'm very much a practical engineer rather than a theoretician. It's 50 years since I did my CS degree. And you know, I'm constantly ...
- 211
18
votes
Theoretical Computer Science vs other Sciences?
As a TCS researcher, I understand the feeling and feel it too sometimes. I think it is healthy to be able to appreciate the wonder that other sciences have to offer.
We must also keep in mind that it ...
- 8,223
25
votes
Theoretical Computer Science vs other Sciences?
As a theoretical computer scientist I am proud of the following achievements of the field.
Logicians figured out that all logical connectives can be build from a single one, paving the road for ...
- 27.5k
5
votes
Turing Machines and Logic
The paper Some Turing-Complete Extensions of First-Order Logic by Antti Kuusisto also provides some examples, where you enrich first-order logic with the ability to modify the input structure, and ...
- 8,223
6
votes
Turing Machines and Logic
Since Turing machines have three options (accept, reject, not halt), you have a few options as to what class of languages correspond to Turing machines. The recursively enumerable sets aren't closed ...
- 209
1
vote
A mathematical (categorical) description of type classes
Here is a categorical description of (certain kinds of) typeclasses. So far, I can fully elaborate this only for simpler typeclasses such as monoids or semigroups, not for type constructor typeclasses ...
- 181
5
votes
Accepted
Shortest path property and monadic second order logic
I'm assuming you want a formula $\varphi(s,t,X)$ in $MSO_2$ on graphs, stating that the set $X$ is the shortest path from $s$ to $t$. Under this meaning of "express the shortest path", no ...
- 8,223
2
votes
How far is the distance between Mahlo Universe and Mahlo Cardinal?
It's awkward to ask yourself questions, but...
Rathjen, M. (2003). Realizing Mahlo set theory in type theory. Archive for Mathematical Logic, 42(1), 89-101.
The chapter 5, "Realizing set theory ...
- 51
Top 50 recent answers are included