893 views

### Can a 1-tape turing machine simulate a stack?

Is it possible to simulate a stack-based machine using a 1-tape turing machine? I cannot wrap my head around it as turing machines do not provide mechanisms such as pointers. I failed to find any ...
• 277
797 views

### Are there any exponential-time iterative algorithms?

Is it possible to implement an exponential-time algorithm using iteration, as opposed to recursion? I didn't have any particular algorithm in mind, I was just thinking theoretically. The way I was ...
2k views

### Does a do-while loop suffice for Turing-completeness?

I know that, in imperative programming languages, a while-do loop is sufficient as a control flow construct to make the language Turing-complete (as far as control flow goes - of course we also need ...
• 633
2k views

### How close are common programming languages to not being Turing complete?

The term "Turing completeness" has been discussed in several of the Computer Science classes that I've taken. However, I've never gotten an intuitive feel for what Turing completeness actually ...
• 193
220 views

### Can a language be Turing Complete if its only provision for unlimited code/memory is through recursion?

We've developed an esoteric language. In this language, a program contains a static amount of code, and a static amount of storage space. However, parts of the program can recurse, so the interpreter ...
• 151
223 views

### Return destinations for an expression-oriented programming language

I am designing a programming language and I want to give everything the ability to return a value. For example, if I use a block as a right-hand side value, I can assign it to a lvalue: ...
397 views

### Smallest set of features that would make relational algebra Turing complete

I'm thinking this should be just one or two things, since lambda calculus is so tiny and still Turing complete. Probably just recursion (something like "MY_QUERY(param) = select * from param UNION ...
• 765
79 views

### Computation equivalence of functional and procedural programming

I'm really interested in the idea of functional programming, it seems like a very modular way of doings things. I've seen some suggestion that functional programming is just as powerful as procedural ...
40 views

### What is minimization (μ-function) in layman tems?

In Computer Science μ-function is used to extend set of primitively recursive functions to generally recursive functions, and I can't understand what this function does. There is a lot of formulae, ...
58 views

### Basic control statements for Turing equivalence? [duplicate]

Apologies ahead of time, I don't fully understand what I'm asking... But, is it possible to program using only 'while loops' and still be Turing equivalent? Or more generally, can I do everything ...
• 15
74 views

### Characterisation of Turing completeness? [duplicate]

I know the definition of a Turing machine but I am trying to find a practical way to characterize a Turing-complete language. For example, an imperative language is Turing complete if it has ...
• 109
665 views

### Understanding the reason behind the μ (mu) operator [closed]

What is the purpose of the $\mu$ operator? Is there a real world example? Is it correct that it can create partial functions out of total functions and it makes a function $g$ with k parameters out ...
• 145
111 views

### Compiling an impure language into a pure stack-based language

For a personal learning and fun project, I build an abstract virtual machine based on a stack. The instructions are simple and act on the top of the stack only. There are also stack operators such as <...
• 255
1 vote
142 views

### Is McCarthy Formalism first ever formalism for defining functions recursively in computer science?

McCarthy formalism is a formalism for defining functions recursively, first introduced in classic paper Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I (1960). ...
• 133