Linked Questions

5 votes
5 answers
2k views

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

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 ...
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 ...
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, ...
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 <...
23 votes
2 answers
6k views

What makes PROLOG Turing-complete?

I know that it can be proven PROLOG is Turing-complete by constructing a program that simulates a Turing machine like this: ...
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). ...
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 ...
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 ...
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: ...
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 ...
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 ...
2 votes
3 answers
1k views

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 ...
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 ...
28 votes
4 answers
5k views

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 ...

15 30 50 per page