Linked Questions

0 votes
2 answers
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 ...
just.kidding's user avatar
0 votes
2 answers
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 ...
Yousuf's user avatar
  • 1
25 votes
1 answer
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 ...
Martin Ender's user avatar
9 votes
1 answer
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 ...
haroba's user avatar
  • 193
5 votes
1 answer
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 ...
Sparr's user avatar
  • 151
3 votes
1 answer
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: ...
Peter Lenkefi's user avatar
3 votes
1 answer
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 ...
Juan's user avatar
  • 765
2 votes
1 answer
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 ...
Java Machine's user avatar
0 votes
1 answer
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, ...
George Shuklin's user avatar
0 votes
1 answer
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 ...
XYZandMe's user avatar
0 votes
1 answer
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 ...
Jerome's user avatar
  • 109
-1 votes
1 answer
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 ...
polym's user avatar
  • 145
2 votes
0 answers
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 <...
Foxy's user avatar
  • 255
1 vote
0 answers
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). ...
Siegmeyer's user avatar
  • 133
0 votes
0 answers
24 views

procedures and immutable data to simulate return values

Let's say I have a programming language that allows procedures, i.e., methods without return values, and immutable data-structures, so no sideeffecting inside a procedure. Is it possible to simulate a ...
Wickoo's user avatar
  • 196

15 30 50 per page