Linked Questions

3 votes
2 answers

If regex describes FSAs, what string formats describe Turing machines?

(Topic summary under the line.) Regex, at least the formal definition featuring only | and *, is used to describe words accepted by a given FSA, but it can be transformed into the corresponding state ...
Tsskyx's user avatar
  • 41
2 votes
1 answer

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

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
2 votes
0 answers

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

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
1 answer

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
5 votes
5 answers

Proof that total computable functions are not enumerable

In an answer to this question, a sketch of the proof that total computable functions are not enumerable is made: Because of diagonalization. If $(f_e:e \in N)$ was a computable enumeration of all ...
agemO's user avatar
  • 177
3 votes
1 answer

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
0 votes
2 answers

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
1 answer

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
2 votes
3 answers

Why does computer have branch and jump instructions

I could guess why computers have arithmetic operations like add, sub, and mult instructions. It is to compute numbers, but I don't get why branch and jump instructions exist. I am asking what theory ...
meBe's user avatar
  • 23
28 votes
4 answers

Why are computable functions also called recursive functions?

In computability theory, computable functions are also called recursive functions. At least at first sight, they do not have anything in common with what you call "recursive" in day-to-day programming ...
Golo Roden's user avatar
25 votes
1 answer

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
0 votes
0 answers

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
5 votes
1 answer

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

15 30 50 per page