The turing-completeness tag has no wiki summary.
1
vote
2answers
43 views
Turing completeness
I encountered the brainfuck programming language which I know is turing complete. However I then decided to create a high level language that gets compiled to brainfuck code.
There is only one data ...
4
votes
1answer
77 views
Natural RE undecidable problems but not Turing-complete
The Halting problem is a natural undecidable language which is complete for the set of recursivly enumrable sets. I am interested in undecidable but not Turing-complete language such that we can not ...
0
votes
3answers
103 views
Looking for some more details on “Turing” devices
I've been reading a lot of computer science literature in the recent past but haven't ran across an explanation of Turing machines, the different types, and why they seem to come up so often (I ...
0
votes
1answer
52 views
To prove Turing-completeness, is it enough to prove capability of producing arbitrary output?
Turing completness is being typically proved via reduction to already proved Turing-complete machine.
Can the same be obtained by showing, that the machine in question is capable of generating ...
4
votes
1answer
214 views
How is the rule 110 Turing complete?
I've read the wikipedia page for rule 110 in cellular automata, and I more or less know how they work (a set of rules decides where to draw the next 1 or 0).
I've just read they're Turing complete, ...
3
votes
3answers
134 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 ...
6
votes
4answers
206 views
Is a device with restrictive execution policies Turing-complete?
There are devices that do not allow users to load any application they want on it, only run a limited class of applications approved by the device vendor.
Take an iPhone as an example where new ...
7
votes
1answer
164 views
Does High Order Functions provide more power to Functional Programming?
I've asked a similar question on cstheory.SE.
According to this answer on Stackoverflow there is an algorithm that on a non-lazy pure functional programming language has an $\Omega(n \log n)$ ...
7
votes
3answers
218 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 ...
15
votes
5answers
933 views
Are there minimum criteria for a programming language being Turing complete?
Does there exist a set of programming language constructs in a programming language in order for it to be considered Turing Complete?
From what I can tell from wikipedia, the language needs to ...
7
votes
2answers
353 views
Universality of the Toffoli gate
Regarding the quantum Toffoli gate:
is it classicaly universal, and if so, why?
is it quantumly universal, and why?
