Linked Questions

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 ...
Golo Roden's user avatar
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
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: ...
Lenar Hoyt's user avatar
19 votes
4 answers
3k views

What is required for universal analogue computation?

What operations need to be performed in order to do any arbitrary analogue computation? Would addition, subtraction, multiplication and division be sufficient? Also, does anyone know exactly what ...
Matthew Matic'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
7 votes
2 answers
1k views

What is the significance of primitive recursive functions?

I was studying the proof of Ackermann function being recursive, but not primitive recursive, and a question hit me: "So what?". Why does it matter? What is the significance of primitive recursive ...
Untitled's user avatar
  • 1,001
6 votes
4 answers
1k views

Do we need recursion in programming language to solve any problem?

My question is simple: If we want to be able to solve every problem, that we can solve using recursions, do we need programming language to allow us use recursions? Assuming we are allowed to use: ...
kravemir's user avatar
  • 202
6 votes
5 answers
2k views

Are if statements unnecessary if a program is represented as an explicit state machine?

This question occurred to me some time ago when I was thinking about whether or not if statements are fundamental in computation. Consider a program that manages a ...
Devian Dover's user avatar
5 votes
4 answers
3k views

Can we write algorithms without conditional statements?

Regarding turing completeness, i read that for a language/machine to be turing complete it is required that it has some sort of conditional. Consider the factorial problem, we would typically define ...
user1508072's user avatar
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
5 votes
3 answers
2k views

What are the minimum requirements for a language to be considered Turing Complete? [duplicate]

Possible Duplicate: Are there minimum criteria for a programming language being Turing complete? I overheard a conversation on the topic and the conclusion that one gent came to was that in order ...
user avatar
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 ...
agemO's user avatar
  • 177
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 ...
Tsskyx's user avatar
  • 41
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
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

15 30 50 per page