New answers tagged

0

Assume we are running program x := e, and let $\sigma$ be the initial state, and $\sigma'$ be the final state. The crucial intuition here is: the value of $x$ in the final state $\sigma'$ is the same as the value of the expression $e$ in the initial state $\sigma$. Indeed, the latter is the value we assign to $x$ with the command x := e. Hence, if $P(-)$ ...


2

There is no interesting relation between a programming language (the set of words which are syntactically valid programs) and the set of words that are accepted by a program written in said programming language. Note that it is possible to design a Turing powerful programming language which, as a formal language, is the set $1^* = \{\epsilon,1,11,111,\ldots\...


2

So after reading and thinking about it more this is my explanation (thanks software foundations): The key confusion for me seems to be the meaning of $P[e/x]$ (replaces every free instance of x with e). What this does is wherever you see the symbol $x$ literally remove it and place $e$. e.g. $ P[e/x] = (x+y+1)[e/x] \to P[e/x] = (e+y+1)$ so notice how $x$ ...


0

https://www.longdom.org/articles/reverse-engineering-turing-machines-and-insights-into-the-collatz-conjecture.pdf is one initial effort to do this for some subclass of Turing machines. Actually there is fantastic culture about it http://bluesky-home.co.uk/. These works almost exclusively cite the author itself, that indicates how undeveloped this field is. ...


-3

If a programming language has "branch (e.g. if)" and "loop (e.g. for/while)", it is Turing-complete, and vice versa. Having "branch" and "loop" is necessary and sufficient conditions for Turing-completeness. Haskell's recursion is a kind of loop.


0

Category theory has certain but limited use for learning functional programming or in actual practice of functional programming. I recently made a presentation to answer that question. https://www.youtube.com/watch?v=Zau8CxsfxOo Summary: Functional programmers do not require category theory in order to master the main features and design patterns that FP ...


1

The relationship between the two is related to intuistionistic logic vs. classical logic. When you add sufficiently powerful versions of the excluded middle law to Curry-Howard-style type systems, you can translate between propositions (types of sort Prop, which are inhabited if and only if they are provable) and Boolean values at will. Check out the list of ...


1

Does it mean that a logic system is a programming language, where types are propositions and values of a type are proofs of the proposition? Not necessarily, being both (logic systems and programming language) formal languages, there certainly is a certain degree of isomorphism between the two concepts, this translates into the fact that we can encode a ...


1

The terminology used in the database area calls the relational algebra “procedural” to contrast it with the languages based on “calculus”, since an algebraic expression describes an ordered set of steps to find the result: simply execute the operations in the correct order to produce the result. In contrast, in an expression of a calculus based language, ...


0

It bears repeating that the algoritm used is most important. An example might be you writing your oen bubble sort on a million records in the worlds fastest language. Compared it to using a really slow language with a built in really good sort. Your fast language will be mighty slow in comparison.


0

There is No need to create a new language. Use as example c. Get a chunk of memory with malloc() and do wharever you wish with it. On a typical operating system today you might need to use low level OS functions of you want to keep the memory from beeing swapped due to virtual memory.


0

Simple answer is, the closer a language is to the hardware the faster it would be. The more a language depends on libraries and other functions to do it's tasks the longer it takes for program execution in that language.


Top 50 recent answers are included