Skip to main content
Share Your Experience: Take the 2024 Developer Survey
33 votes
Accepted

Can we ever achieve Turing completeness?

As far as I know we say something is turing complete (eg: a programming language) when it can compute any function and can do any task. No. A model of computation is Turing-complete if it can compute ...
Jörg W Mittag's user avatar
12 votes

What are the conditions necessary for a programming language to have no undefined behavior?

First off, let's be clear on what "undefined behaviour" is. In just C alone (and this is the understanding inherited by C++), there are two possible meanings, depending on which version of ...
Pseudonym's user avatar
  • 22.2k
11 votes

Does the first incompleteness theorem imply that any Turing complete programming language must have undefined behavior?

No, it doesn't require that. These are two orthogonal issues. You can easily define a new programming language where you provide fully defined semantics for all operations; yet it can be Turing ...
D.W.'s user avatar
  • 160k
8 votes

What are the conditions necessary for a programming language to have no undefined behavior?

The C language may say "if you do X, then whatever the result is, is not a violation of the C Standard". "Whatever the result is" can include the result that you hoped for, some ...
gnasher729's user avatar
  • 30.4k
5 votes

Is there a theoretical foundation behind CSS?

Selectors and combinators from CSS are a form of combinatory logic. This can be reduced to the SKI calculus. I think it is also possible to see CSS rulesets as a form of lenses from functional ...
tykom's user avatar
  • 51
5 votes
Accepted

Is there a theoretical foundation behind CSS?

I don't think there is a deeper foundation, as CSS is just a lookup table of key value pairs declared under certain rules. It then gets interpreted by the browsers' graphical renderer. From a ...
iGoodie's user avatar
  • 74
5 votes
Accepted

What is the closest theory to "The theory of code refactoring"?

Basic code refactoring is not about symmetries but rather about equivalences. When code $C$ is transformed by refactoring to become code $C'$, we expect $C$ and $C'$ to "do the same thing". (...
Andrej Bauer's user avatar
  • 30.5k
5 votes
Accepted

What are the conditions necessary for a programming language to have no undefined behavior?

The problem of statically detecting undefined behavior has nothing to do with undefinedness as such. It's just impossible to prove in general that programs in a Turing-complete language will do ...
benrg's user avatar
  • 2,147
4 votes

Does the first incompleteness theorem imply that any Turing complete programming language must have undefined behavior?

Your intuition is incorrect. The analogies you're trying to draw are not there, even though it's understandable you would expect them. Programming languages can be defined as formal systems, but they ...
Andrej Bauer's user avatar
  • 30.5k
4 votes

What are the conditions necessary for a programming language to have no undefined behavior?

So my question now is, what conditions need to be imposed on a Turing complete language in order to guarantee that all possible programs written in the language will have fully defined behavior ...
yeputons's user avatar
  • 256
4 votes

Can we ever achieve Turing completeness?

Disclaimer: Please double check everything in this answer, because I am no expert on the topic. The Halting problem is not a necessary condition for Turing completeness. On the contrary: the Turing ...
DirkT's user avatar
  • 991
3 votes

What are the conditions necessary for a programming language to have no undefined behavior?

Lets look at a sample program ...
QuadmasterXLII's user avatar
3 votes

Named outputs of a function

Golang has this feature (named return values): ...
Sadeq's user avatar
  • 131
3 votes

What are the conditions necessary for a programming language to have no undefined behavior?

Starting from the C/C++ languages, ruling out all undefined behavior would be very hard. But if you're designing a language from scratch, it's not difficult at all to rule out undefined behavior. Many ...
Glenn Willen's user avatar
3 votes
Accepted

How to prove a function is a bijection (name mangling)?

Let $\Sigma$ be an alphabet including underscore, decimal digits, letters, and parentheses (e.g. the printable ASCII characters). Define a mangling function $f:(\Sigma^* \times \Sigma^*) \to \Sigma^*$ ...
Kai's user avatar
  • 908
2 votes

Does the first incompleteness theorem imply that any Turing complete programming language must have undefined behavior?

The incompleteness theorem only applies to formal systems that can express a certain amount of arithmetic. In particular, they have to support statements of the form $\forall n\in\mathbb N. P(n)$, ...
benrg's user avatar
  • 2,147
2 votes

Datatypes and number representaton

Let us do 8-bit numbers, it's less writing. The left-most bit is not the sign. It contributes $-128$ to the value. More precisely, here are the values of the bits, where bit 0 is the right-most one ...
Andrej Bauer's user avatar
  • 30.5k
2 votes
Accepted

Show that if <S1;S2,s> => * s', it is not necessarily the case that <S1,s> =>* s'

The proof you give is a counterexample of the reciprocal. That is, you're giving an example where $\langle S_1, s\rangle \Rightarrow^* s'$ but not $\langle S_1; S_2, s\rangle \Rightarrow^* s'$. To ...
Carlos Miguel Soto's user avatar
2 votes

How to evaluate an arbitrary mathematical expression

Well, this is a common problem, that is used similarly for making a programming language. I do not know exactly what branch is belongs to, my guess would be something similar to computational ...
Thobias Larsen's user avatar
2 votes
Accepted

how to do incremental construction of the minimal model in logic programming?

this paragraph describes the immediate consequences operator $T_P(I) = \{ a \mid \text{there exists a rule } r \in G(P) \text{ with } head(r)=a \text{ and } body(r) \subseteq I \}$ for some ...
jt0202's user avatar
  • 171
2 votes

Can you verify the end of a function declaration through syntax analysis?

It depends on what is meant by a syntax analyzer. Generally, in computer science, different people often mean different things by the same term, so always consult the definition you were given. It is ...
reinierpost's user avatar
  • 5,664
2 votes

Returning more than one value from a function without overhead

Modern compilers are quite capable of optimizing a tuple return value so that the result is passed in registers, or in an unpacked form on the stack. In addition, even when this is not the case, ...
Andrej Bauer's user avatar
  • 30.5k
2 votes
Accepted

How did this work apply weakest precondition rule on their example car problem?

Let's address your questions/confusions in order: 1. I don't see the authors working on the former equation, only the latter. That's because $x$ doesn't matter: it does not occur in the ...
Kai's user avatar
  • 908
2 votes

Creating an executable after code generation - compiler design

Assembly language is basically meant to be a 1:1 representation of the underlying CPU machine code. (Yes I'm aware there are a few exceptions, especially with modern assemblers) The difference is you ...
Caleb Fuller's user avatar
2 votes
Accepted

What is the precise difference between state and environment and memory?

Very informally: An environment is a set of pairs (variable+value) that are accessible to a particular object/process during its execution. A memory is a set of "locations" in which an ...
Vor's user avatar
  • 12.5k
1 vote

In the simulation of a C-program by a Turing machine, how does a TM determine which instruction to execute?

The tape of the TM stores the code of the program (the sequence of machine instructions), followed by the memory of the program. You design a TM that traverses back and forth between the code section ...
D.W.'s user avatar
  • 160k
1 vote

Is there any reference materials on complexity analysis for lazy languages?

You could do worse than Chris Okasaki's Purely Functional Data Structures. It was published as a book, but here's the thesis version. Another couple of theses that I haven't read, but may be worth ...
Pseudonym's user avatar
  • 22.2k

Only top scored, non community-wiki answers of a minimum length are eligible