Software Engineering Stack Exchange
Software Engineering Stack Exchange

Questions tagged [turing-completeness]

26 questions
104
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,115
  • 2
  • 8
  • 3
73
votes
6 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,832
  • 3
  • 49
  • 62
39
votes
8 answers

Is it actually possible to have a 'useful' programming language that isn't Turing complete?

Where it is accepted that a language has to be Turing complete to be any good, is it actually possible to have a 'useful' programming language that isn't Turing complete? I should clarify that this is quite specifically about 'programming' languages…
PhonicUK
  • 1,047
  • 3
  • 11
  • 12
37
votes
5 answers

What is the absolute minimum set of instructions required to build a Turing complete processor

I have a general idea of how the processor handles instructions but spend my time working in mostly high level languages. Maybe somebody who works closer to the iron can provide some valuable insight. Assuming that programming languages are…
Evan Plaice
  • 5,725
  • 2
  • 24
  • 34
20
votes
2 answers

Are there mainstream general-purpose non-Turing complete languages available today?

Non-Turing complete languages offer a great advantage over Turing-complete languages as they are much more analyzable and, thus, offer much broader optimization possibilities. Yet they are barely used and Turing-completeness is actually sold as a…
MaiaVictor
  • 5,820
  • 7
  • 27
  • 45
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
  • 5
  • 41
  • 62
17
votes
5 answers

Is there a programming language where every string is a valid program?

Does there exist a Turing complete programming language such that for a fixed alphabet (say, ASCII), every possible permutation of those characters is a semantically valid program capable of being executed? We consider infinite loops to also be…
mp-
  • 287
  • 1
  • 2
13
votes
5 answers

Can *any* program task be expressed without state?

This is a theoretical question, but after many years of programming in what I now realize is "normal" imperative technique, using C++ mainly, I've discovered this other world of functional programming, which I stumbled upon accidentally while…
johnbakers
  • 289
  • 1
  • 7
11
votes
2 answers

How is Brainfuck Turing complete?

I'm trying to write a bit of code in Brainfuck, but I stumbled into some problems. That got me wondering how Brainfuck is Turing complete, as I understand it Turing complete means a language or machine can calculate any function. What got me…
S.Klumpers
  • 237
  • 2
  • 7
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
7
votes
1 answer

Are non Turing-complete languages considered programming languages at all?

Reading a recent question: Is it actually possible to have a 'useful' programming language that isn't Turing complete?, I've come to wonder whether non Turing-complete programming languages are considered programming languages at all. Since…
Tulains Córdova
  • 39,201
  • 12
  • 97
  • 154
7
votes
3 answers

Quantum computers and Turing Machine

As far as I know, a Turing Machine is the widely used model in computational theory to know whether something could be computed and if computed can they can be computed in finite time (P, NP, NPSpace). But I have the following doubts: Is a Turing…
Ubermensch
  • 1,349
  • 9
  • 15
4
votes
4 answers

Is a call stack required for robust computer architecture?

I am not too familiar with the computer architecture terminology yet so please bear with me. I seem to understand that von Neumann architectures are more robust ("universal Turing machines") as opposed to Harvard architectures, but don't know too…
Lance
  • 2,537
  • 15
  • 34
4
votes
6 answers

Does a programming language have to be compiled to be considered a programming language?

A person I met recently had an argument. It was that a programming language had to be compiled to be considered a programming language. This would make HTML/CSS (unless you're using SCSS or LESS) not a programming language. So, does it have to be…
StackExchange User
  • 143
  • 5
3
votes
1 answer

What was the first mechanical Turing-complete machine ever constructed?

We know that Charles Babbage designed the first Turing-complete mechanical machine - the Analytical Engine - in the 1800s, but it was never actually built (not yet anyway). In recent history, at least one mechanical Turing machine has been built. …
joeytwiddle
  • 265
  • 1
  • 4
1
2