User Martin Berger

104 votes

Accepted

What is the contribution of lambda calculus to the field of theory of computation?

answered Mar 23, 2014 at 20:25

45 votes

P and NP classes explanation through lambda-calculus

cc.complexity-theory complexity-classes turing-machines lambda-calculus

answered Jun 6, 2014 at 9:08

37 votes

Applicability of Church-Turing thesis to interactive models of computation

computability turing-machines machine-models church-turing-thesis

answered Aug 29, 2012 at 10:01

34 votes

Books on programming language semantics

reference-request pl.programming-languages semantics denotational-semantics books

answered Dec 5, 2010 at 17:09

26 votes

Accepted

What's the difference between term rewriting and pattern matching?

pl.programming-languages terminology term-rewriting-systems

answered Apr 26, 2011 at 20:28

26 votes

Accepted

Research and open challenges in Programming Language Theory

pl.programming-languages open-problem research-practice

answered Jun 2, 2013 at 5:59

24 votes

Accepted

Why was there a need for Martin-Löf to create intuitionistic type theory?

lo.logic soft-question type-theory big-picture ho.history-overview

answered Mar 1, 2015 at 21:41

19 votes

Accepted

Why is Proof Checker required in Proof Carrying Code

proof-theory automated-theorem-proving program-verification

answered Aug 30, 2015 at 16:51

19 votes

Historical reasons for adoption of Turing Machine as primary model of computation.

reference-request soft-question computability turing-machines ho.history-overview

answered Dec 9, 2010 at 13:10

19 votes

What constitutes denotational semantics?

pl.programming-languages big-picture semantics denotational-semantics

answered Dec 6, 2010 at 13:38

19 votes

Accepted

(How) can you model broadcasts in the pi-calculus?

pl.programming-languages formal-modeling process-algebra pi-calculus

answered Mar 19, 2012 at 14:06

17 votes

How important is knowing how to program for TCS?

soft-question big-list advice-request career

answered Nov 9, 2011 at 12:15

17 votes

Accepted

Is it a Known Concept to Compute an Algorithm Once and Re-Interpret Answer for Different Inputs

reference-request terminology

answered Sep 7, 2015 at 19:58

17 votes

Lipton's most influential results

big-list

answered Sep 16, 2014 at 9:49

17 votes

Math talk: Theorem about git revision control system?

co.combinatorics application-of-theory

answered Aug 26, 2015 at 8:04

16 votes

Accepted

Equivalent formulation of complexity theory in Lambda Calculus?

time-complexity lambda-calculus

answered Oct 23, 2018 at 11:54

16 votes

What is the "question" that programming language theory is trying to answer?

soft-question pl.programming-languages lambda-calculus big-picture combinatory-logic

answered Apr 16, 2019 at 8:51

15 votes

Algebra oriented branch of theoretical computer science

soft-question algebra advice-request ct.category-theory

answered Sep 23, 2014 at 14:19

15 votes

Accepted

Program reasoning about own source code

pl.programming-languages ai.artificial-intel recursion

answered Sep 4, 2015 at 17:38

13 votes

Humanifying computer-generated or computer assisted proofs

proofs proof-assistants

answered Jul 23, 2015 at 11:18

13 votes

Accepted

Are there any annotated formal verification systems for pure functional programming languages?

lo.logic pl.programming-languages functional-programming formal-methods haskell

answered Sep 19, 2014 at 17:46

13 votes

Accepted

How can I prove formally semantic equivalence of programming languages?

reference-request pl.programming-languages semantics equivalence

answered Mar 30, 2014 at 11:18

12 votes

Abstract algebra for Theoretical Computer Scientists

soft-question algebra teaching

answered Feb 24, 2013 at 21:05

12 votes

Accepted

Good books on parser theory?

research-practice books parsing

answered Dec 2, 2014 at 15:17

12 votes

Are there any topics in theoretical CS that are more about pure math?

reference-request soft-question

answered May 4, 2015 at 4:55

12 votes

Accepted

Logical framework vs type theory

lo.logic type-theory

answered Feb 18, 2015 at 20:42

12 votes

Is there a theory that combines category theory/abstract algebra and computational complexity?

cc.complexity-theory algebra algebraic-complexity

answered Jul 22, 2015 at 12:08

11 votes

What functions can System F not compute?

computability turing-machines haskell

answered Feb 18, 2015 at 1:02

11 votes

Accepted

"Correctness" of type theory

lo.logic type-theory dependent-type

answered Apr 4, 2014 at 19:46

11 votes

Accepted

What is the intuition behind linear logic?

lo.logic type-theory linear-logic

answered Jul 15, 2017 at 9:40

Stack Exchange Network

current community

your communities

more stack exchange communities

96 Answers

What is the contribution of lambda calculus to the field of theory of computation?

P and NP classes explanation through lambda-calculus

Applicability of Church-Turing thesis to interactive models of computation

Books on programming language semantics

What's the difference between term rewriting and pattern matching?

Research and open challenges in Programming Language Theory

Why was there a need for Martin-Löf to create intuitionistic type theory?

Why is Proof Checker required in Proof Carrying Code

Historical reasons for adoption of Turing Machine as primary model of computation.

What constitutes denotational semantics?

(How) can you model broadcasts in the pi-calculus?

How important is knowing how to program for TCS?

Is it a Known Concept to Compute an Algorithm Once and Re-Interpret Answer for Different Inputs

Lipton's most influential results

Math talk: Theorem about git revision control system?

Equivalent formulation of complexity theory in Lambda Calculus?

What is the "question" that programming language theory is trying to answer?

Algebra oriented branch of theoretical computer science

Program reasoning about own source code

Humanifying computer-generated or computer assisted proofs

Are there any annotated formal verification systems for pure functional programming languages?

How can I prove formally semantic equivalence of programming languages?

Abstract algebra for Theoretical Computer Scientists

Good books on parser theory?

Are there any topics in theoretical CS that are more about pure math?

Logical framework vs type theory

Is there a theory that combines category theory/abstract algebra and computational complexity?

What functions can System F not compute?

"Correctness" of type theory

What is the intuition behind linear logic?