Stack Overflow
Stack Overflow

Questions tagged [turing-complete]

A model of computation is called Turing-complete if it is capable of simulating a Turing machine. Programming languages that are Turing complete are at least as powerful as the most powerful models of feasible computation yet theorized.

A Turing Complete system means a system in which a program can be written that will find an answer (although with no guarantees regarding runtime or memory) 1.

116 questions
692
votes
14 answers

What is Turing Complete?

What does the expression "Turing Complete" mean? Can you give a simple explanation, without going into too many theoretical details?
dlinsin
  • 19,249
  • 13
  • 42
  • 53
384
votes
7 answers

Is CSS Turing complete?

CSS isn't, insofar as I know, Turing complete. But my knowledge of CSS is very limited. Is CSS Turing complete? Are any of the existing draft or committees considering language features that might enable Turing completeness if it isn't right…
Adam Davis
  • 91,931
  • 60
  • 264
  • 330
139
votes
12 answers

C++ templates Turing-complete?

I'm told that the template system in C++ is Turing-complete at compile time. This is mentioned in this post and also on wikipedia. Can you provide a nontrivial example of a computation that exploits this property? Is this fact useful in practice?
Federico A. Ramponi
  • 46,145
  • 29
  • 109
  • 133
94
votes
6 answers

I've heard that LaTeX is Turing complete. Are there any programs written in LaTeX?

It's possible to do interesting things with what would ordinarily be thought of as typesetting languages. For example, you can construct the Mandelbrot set using postscript. It is suggested in this MathOverflow question that LaTeX may be…
ire_and_curses
  • 68,372
  • 23
  • 116
  • 141
88
votes
4 answers

Is the C99 preprocessor Turing complete?

After discovering the Boost preprocessor's capabilities I found myself wondering: Is the C99 preprocessor Turing complete? If not, what does it lack to not qualify?
Anycorn
  • 50,217
  • 42
  • 167
  • 261
70
votes
4 answers

What are the practical limitations of a non-turing complete language like Coq?

As there are non-Turing complete languages out there, and given I didn't study Comp Sci at university, could someone explain something that a Turing-incomplete language (like Coq) cannot do? Or is the completeness/incompleteness of no real practical…
oxbow_lakes
  • 133,303
  • 56
  • 317
  • 449
67
votes
5 answers

Why can Conway’s Game of Life be classified as a universal machine?

I was recently reading about artificial life and came across the statement, "Conway’s Game of Life demonstrates enough complexity to be classified as a universal machine." I only had a rough understanding of what a universal machine is, and…
Ziggy
  • 21,845
  • 28
  • 75
  • 104
66
votes
11 answers

How useful is Turing completeness? are neural nets turing complete?

While reading some papers about the Turing completeness of recurrent neural nets (for example: Turing computability with neural nets, Hava T. Siegelmann and Eduardo D. Sontag, 1991), I got the feeling that the proof which was given there was not…
Albert
  • 65,406
  • 61
  • 242
  • 386
59
votes
3 answers

Are Perl regexes turing complete?

I've seen Ruby and Perl programmers do some complicated code challenges entirely with regexes. The lookahead and lookbehind capabilities in Perl regexes make them more powerful than the regex implementations in most other languages. I was wondering…
Peter Olson
  • 139,199
  • 49
  • 202
  • 242
58
votes
2 answers

The type system in Scala is Turing complete. Proof? Example? Benefits?

There are claims that Scala's type system is Turing complete. My questions are: Is there a formal proof for this? How would a simple computation look like in the Scala type system? Is this of any benefit to Scala - the language? Is this making…
Adrian
  • 3,762
  • 2
  • 31
  • 40
58
votes
3 answers

Is HTML Turing Complete?

After reading this question Is CSS Turing complete? -- which received a few thoughtful, succinct answers -- it made me wonder: Is HTML Turing Complete? Although the short answer is a definitive Yes or No, please also provide a short description or…
Luke
  • 18,811
  • 16
  • 99
  • 115
56
votes
8 answers

Practical non-Turing-complete languages?

Nearly all programming languages used are Turing Complete, and while this affords the language to represent any computable algorithm, it also comes with its own set of problems. Seeing as all the algorithms I write are intended to halt, I would like…
Kyle Cronin
  • 77,653
  • 43
  • 148
  • 164
54
votes
2 answers

Are makefiles Turing complete?

Lately at work, I've been doing some translation from Makefiles to an alternative build system. I've seen some pretty hairy Make code in some places using functional map, filter, and foreach constructs. This surprised me since I think build scripts…
Jay Conrod
  • 28,943
  • 19
  • 98
  • 110
52
votes
13 answers

What are practical guidelines for evaluating a language's "Turing Completeness"?

I've read "what-is-turing-complete" and the wikipedia page, but I'm less interested in a formal proof than in the practical implications of requirements for being Turing Complete. What I'm actually trying to decide is if the toy language I've just…
AShelly
  • 34,686
  • 15
  • 91
  • 152
49
votes
1 answer

How did Haskell add Turing-completeness to System F?

I've been reading up on various type systems and lambda calculi, and i see that all of the typed lambda calculi in the lambda cube are strongly normalizing rather than Turing equivalent. This includes System F, the simply typed lambda calculus plus…
JwameeQohwiye
  • 603
  • 5
  • 6
1
2 3 4 5 6 7 8