Linked Questions

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
0 votes
1 answer
68 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
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
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
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
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
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
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
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
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
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
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 ...
meBe's user avatar
  • 23
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
0 votes
2 answers
878 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

15 30 50 per page