Questions tagged [turing-completeness]
26 questions
106
votes
7 answers
What makes a language Turing-complete?
What is the minimal set of language features/structures that make it Turing-complete?
Curious Cat
- 1,135
74
votes
7 answers
Is musical notation Turing-Complete?
I'm wondering, is music notation language Turing-Complete?
My first thought is that there are loops in musical notation, but there is no way to write conditional branches, right?
I'm not a musician, so perhaps someone can help fill in the gaps?
Klaim
- 14,862
- 4
- 50
- 62
18
votes
4 answers
Measure of power other than Turing completeness
I originally tried asking this on StackOverflow, but it was too subjective :-(. I am interested in methods of defining the power of programming languages. Turing completeness is one, but it is almost universally satisfied. What would be nice is to…
Casebash
- 7,662
11
votes
1 answer
Why is FRACTRAN turing complete?
I've tried to google for explanation but most links only say things like "FRACTRAN is turing complete. As an example, let's look at multiplication."
I remember seeing an xkcd forum post say that FRACTRAN helped the poster understand Turing…
mage
3
votes
3 answers
Is APL a Turing-complete language?
On the Wikipedia page for APL, I haven't been able to find any mention of the language being Turing-complete, although it does (to my incomplete understanding of TC) appear to be capable of performing any possible calculation.
Can anyone elucidate?
user181135
2
votes
2 answers
Is this language Turing-Complete?
I recently made an esoteric programming language, and I want to know how to test and see if the language is Turing-Complete. Most places I looked said it needed infinite loops and infinite data storage. Is that all?
Also, do I need to simulate a…
Dylan Turner
- 141
- 5
-7
votes
1 answer
Is a language which terminates in a given amount of real-time still Turing complete?
Background: You think the halting problem is silly. Let's solve it. Your solution? You create a program compiler which will always terminate compiled programs in an arbitrary, finite, determinate amount of time t. If the number of clock…
tuskiomi
- 103