The tag has no wiki summary.

learn more… | top users | synonyms

0
votes
2answers
111 views

What are the consequences of Hash-Life running in O(log n)?

After reading about the HashLife algorithm, I found that it runs in O(log n). The Game of Life is also Turing Complete, so in theory we should be able to run any algorithm on a "computer" constructed ...
0
votes
3answers
115 views

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. ...
8
votes
1answer
252 views

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 ...
7
votes
2answers
595 views

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 ...
2
votes
0answers
119 views

Are there non-turing complete dynamic languages which can be used to create useful programs? [duplicate]

While it takes a turing complete language to create any imaginable program, is it possible to compute most "useful" programs with a non-turing complete dynamically typed language? For example, is ...
1
vote
2answers
632 views

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 ...
2
votes
1answer
219 views

Why are there non-decidable languages? Can anyone explain me my book's solution?

Well in my book it is says that "there are non-decidable languages" And the proof is: Every algorithm is a word. Then there are only countable algorithms. But there are uncountable languages and ...
0
votes
3answers
816 views

If all programming languages are Turing Complete then why do we have language wars? [closed]

There are language wars saying one programming language is better than other.. Consider Lisp and Java; and we can argue that the meta programming capabilities of Lisp is better than that of Java. But ...
6
votes
1answer
630 views

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 ...
26
votes
5answers
2k views

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 ...
1
vote
2answers
218 views

Can the Turing machine be classified?

Can the Turing machine be classified e.g. as a Mealy machine? Why not? Can a Turing machine be input to another Turing machine without complication like halting problems? Thanks
1
vote
2answers
512 views

Programming Language, Turing Completeness and Turing Machine

A programming language is said to be Turing Completeness if it can successfully simulate a universal TM. Let's take functional programming language for example. In functional programming, function ...
6
votes
2answers
798 views

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, ...
2
votes
2answers
556 views

What are complete programming languages with a minimal syntax and how is that important? [closed]

With minimal syntax I mean a language that could be entirely described with the least words possible, but complete enough to make any kind of program.
48
votes
6answers
3k views

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 ...
22
votes
5answers
6k views

What makes a language Turing-complete?

What is the minimal set of language features/structures that make it Turing-complete?
15
votes
4answers
629 views

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 ...