# Tag Info

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 ...

### 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

### 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

### 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

### 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 ...
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

### 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

### 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

### 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

### 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

### 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

### 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

### 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

### 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
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 ...