Questions tagged [turing-completeness]
The turing-completeness tag has no usage guidance.
26
questions
-4
votes
1
answer
78
views
Is a language which terminates in a given amount of real-time still Turing complete for all finite problems?
Background: this is a continuation of this question here, further expanding the thought experiment.
In short, you have a magic calculation machine which has the following properties.
The machine is:
...
- 103
-7
votes
1
answer
115
views
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 ...
- 103
4
votes
4
answers
2k
views
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 ...
- 2,412
16
votes
5
answers
784
views
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 ...
- 277
-2
votes
1
answer
474
views
Is operating system Universal Turing Machine?
The definition of UTM(Universal Turing Machine) is a Turing machine that can
simulate other Turing machines, so as far as I can guess operating system is a
UTM, since it can run multiple programs on a ...
- 13
2
votes
2
answers
778
views
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 ...
- 141
10
votes
2
answers
6k
views
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 ...
- 227
3
votes
0
answers
728
views
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 ...
- 265
2
votes
1
answer
585
views
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 ...
user181135
3
votes
5
answers
797
views
Does it make sense to say if an OS is Turing complete
The book "Modern Operating systems",
says
The Operating System is an Extended Machine.
So I wonder if an OS is a model of computaion, and whether it makes sense to say if an OS is Turing complete?...
- 5,271
3
votes
3
answers
1k
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 ...
- 181
26
votes
5
answers
20k
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.
...
- 5,625
10
votes
1
answer
2k
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 ...
mage
13
votes
5
answers
1k
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 programming,...
- 289
2
votes
0
answers
135
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 ...
- 5,680
19
votes
2
answers
16k
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 ...
- 5,680
3
votes
1
answer
339
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 ...
4
votes
6
answers
719
views
Does a programming language have to be compiled to be considered a programming language? [duplicate]
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 ...
7
votes
1
answer
2k
views
Are non Turing-complete languages considered programming languages at all? [closed]
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 ...
- 38.7k
39
votes
8
answers
6k
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,047
-1
votes
2
answers
342
views
Can the Turing machine be classified? [closed]
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
- 7,798
0
votes
2
answers
1k
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 ...
- 824
7
votes
3
answers
5k
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, NPSpace)....
- 1,359
71
votes
6
answers
9k
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 musician,...
- 14.6k
96
votes
7
answers
58k
views
What makes a language Turing-complete?
What is the minimal set of language features/structures that make it Turing-complete?
- 1,035
18
votes
4
answers
1k
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 ...
- 7,602