The tag has no usage guidance.

learn more… | top users | synonyms

4
votes
5answers
569 views

Is there any example of automatas (or similar) systems that emerge complex internal structures on its own?

Automatas are turing-complete grid-based systems with progression rules on which we can encode arbitrarily complex structures. For example, this is a "glider gun" on Conway's Game of Life: Due to ...
1
vote
1answer
29 views

Simplest Turing-complete ruleset for Markov algorithm

Is there an example of a particular ruleset for a Markov algorithm that is Turing-complete? If so, what is the simplest example of such a ruleset?
14
votes
5answers
2k views

Why can functional languages be defined as Turing complete?

Perhaps my limited understanding of the subject is incorrect, but this is what I understand so far: Functional programming is based off of Lambda Calculus, formulated by Alonzo Church. Imperative ...
0
votes
1answer
23 views

FSM + state data is Turing complete abstraction?

I'm playing with Akka FSM. The declaration of a an Akka FSM consists of states + data mantained during the states (the akka doc is more clear than me) + events that trigger transitions between states. ...
5
votes
1answer
60 views

Can a language be Turing Complete if its only provision for unlimited code/memory is through recursion?

We've developed an esoteric language. In this language, a program contains a static amount of code, and a static amount of storage space. However, parts of the program can recurse, so the interpreter ...
6
votes
1answer
102 views

How can a universal Turing machine simulate “bigger” ones?

I'm trying to find the answers of two questions about the Universal Turing machine. How can the Universal Turing machine simulate a Turing machine if the one that is being simulated has a bigger ...
4
votes
1answer
61 views

Is a LBA with stack more powerful than a LBA without?

Even so a linear bounded automata (LBA) is strictly more powerful than a pushdown automata (PDA), adding a stack to a LBA might make it more powerful. A LBA with stack should not be Turing complete, ...
3
votes
5answers
641 views

Do we need recursion in programming language to solve any problem?

My question is simple: If we want to be able to solve every problem, that we can solve using recursions, do we need programming language to allow us use recursions? Assuming we are allowed to use: ...
5
votes
2answers
252 views

Is a stack machine with a forward read iterator Turing complete?

It is well known that a machine with a single stack as only unlimited storage is not Turing complete, if it can only read from the top of the stack. I want a machine which is (slightly) more powerful ...
1
vote
1answer
39 views

np-complete proof, turing reduction

I have some difficulties with a complexity proof : I work with 3 problems : A, B and C I know : A-> B A-> C C -> B A-> B meaning : if I have a "yes answer " for A , then I have a "yes answer" for ...
5
votes
4answers
1k views

Can we write algorithms without conditional statements?

Regarding turing completeness, i read that for a language/machine to be turing complete it is required that it has some sort of conditional. Consider the factorial problem, we would typically define ...
1
vote
1answer
70 views

Does stay put TM recognizes same languages as standard TM

I am reading this text book and it says that stay put turing machine recognizes the same languages as regular turing machine by just adding transition functions (without adding any new states or ...
19
votes
3answers
3k views

Can regular languages be Turing complete?

I was reading about Iota and Jot and found this section confusing: Unlike Iota, where the syntactic tree for a string can branch either on the left or on the right, Jot syntax is uniformly ...
3
votes
1answer
59 views

Are fixed-point combinators general recursive?

I don't know if I'm using the vocabulary correctly, but what I'm interested in is this: If your language has fixed-point combinators, is it Turing-complete?
3
votes
2answers
193 views

Finite number of Turing machines running concurrently on multi-tapes Turing-machine-equivalent?

So basically, there are several (finite number of) Turing machines being able to read off and write to the same set of tapes (the number of tapes is finite, but each tape may have infinite tape ...
1
vote
1answer
77 views

Are conditionals necessary in computation? [duplicate]

I know this question might seem weird, maybe I'm just overthinking, but this is really troubling me because I've been a computer engineer for some time now and conditionals (if statements for ...
7
votes
0answers
75 views

Is There a Complete Problem for the Class of Turing Decidable Problems?

Languages such as $\text{HALT}_{TM}$ are $\textsf{RE-complete}$ under many-one reductions. It is trivial to see that $\text{co-RE}$ has complete problems, too. S. Schmitz [1] considers some classes ...
4
votes
3answers
493 views

Rice's theorem vs Turing completeness

I would like to clarify this because I see some kind of contradiction between Rice's theorem and Turing completeness. This is the problem: In building an Universal Turing Machine to emulate another ...
5
votes
1answer
334 views

Is model theory useful for computer scientists

It is often stated in the CS folklore that Turing was inspired by Gödel's incompleteness theorem, more specifically the diagonalization proof and the isomorphism between axiomatically generated ...
0
votes
1answer
43 views

Two functions which can create any computable function by composing?

Do there exist two computable functions, a and b, which can construct every computable function by a finite serie of a's and b's which is function composed? Fx. let's take the serie, a,b,a,b,b,a,a,a , ...
4
votes
2answers
258 views

Are Boolean functions Turing complete

A Boolean function is a function $f:\{0,1\}^n\rightarrow\{0,1\}$. The boolean basis $(\vee,\wedge)$ is known to be Turing complete as it allows any sequence $s\in\{0,1\}$ to be flipped or to be left ...
0
votes
0answers
101 views

How to simulate a cellular automaton via a Turing machine

It is rather easy to see that every cellular automaton can be simulated by a Turing machine: We can simulate a cellular automaton with an appropriate C program and every C program can be simulated by ...
3
votes
1answer
125 views

Is a Turing Machine that only takes strings of the form $0^*$ Turing Complete?

You have a Turing machine that only processes input on the form $0^*$. If it is given an input without 0's, it will simply halt without accepting or do anything else. Is it Turing Complete? The set ...
1
vote
2answers
161 views

If a DFA can be simulated by a real program, can it be simulated by a TM

In proofs of decidability, we often want to simulate another model of computation by a Turing machine. But if I can simulate a $\mathsf{DFA}$ by, say, a C program, then is there some result which says ...
1
vote
1answer
141 views

Simulating a TM with a 2-head, right moving TM

Is it possible to simulate a regular Turing Machine with a TM with the following specs? There are two heads, one of which can read, one of which can write Both heads can only move right When a head ...
6
votes
1answer
254 views

How close are common programming languages to not being Turing complete?

The term "Turing completeness" has been discussed in several of the Computer Science classes that I've taken. However, I've never gotten an intuitive feel for what Turing completeness actually ...
9
votes
1answer
683 views

Is any language that can express its own compiler Turing-complete?

A comment over on tex.SE made me wonder. The statement is essentially: If I can write a compiler for language X in language X, then X is Turing-complete. In computability and formal languages ...
7
votes
1answer
565 views

What makes PROLOG Turing-complete?

I know that it can be proven PROLOG is Turing-complete by constructing a program that simulates a Turing machine like this: ...
2
votes
1answer
130 views

Would adding recursive named functions to Simply typed lambda calculus make it Turing complete?

Say I have Simply typed lambda calculus, and add an assignment rule: <identifier> : <type> = <abstraction> Where ...
5
votes
0answers
95 views

On the Turing Completeness of First Order Logic

It is well known that in Descriptive Complexity Theory FO is equivalent to AC0. However, this accepts a couple of a theory and a string <T,s> iff the ...
1
vote
0answers
149 views

Are QR codes Turing-complete under the rules of Conway's Game of Life?

This is a bit of a weird question, but I was wondering earlier if QR codes are Turing-complete when interpreted as initial states for Conway's Game of Life. My intuition is "yes", as there are ...
1
vote
1answer
184 views

How do you say when a language is Turing-complete only in a trivial way?

I didn't know how to ask this question before but now that I'm reading about typed lambda calculus I think I've got a better idea. There is this answer to a question asking whether CSS is Turing ...
6
votes
2answers
650 views

Clear, complete, proof that a language is Turing Compete?

I have seen web sites that purport to "prove" that HTML5+CSS is Turing Complete. I have seen web sites that purport to "prove" that SQL is Turing Complete. I have seen a bunch of web sites that ...
1
vote
0answers
70 views

Smallest set of features that would make relational algebra Turing complete

I'm thinking this should be just one or two things, since lambda calculus is so tiny and still Turing complete. Probably just recursion (something like "MY_QUERY(param) = select * from param UNION ...
3
votes
2answers
848 views

Does a Universal Turing Machine have more computational power than a non-universal one?

I'm a bit confused about these concepts. As far as I understand, something is Turing complete when it can simulate a Turing machine. And there is this thing called a Universal Turing machine which is ...
0
votes
1answer
242 views

Class of the language of Turing machines that loop on at least one input

$L = \{ \langle M \rangle \mid \text{there is at least one input string on which the \(M\) does not halt} \}$ Here, for a Turing machine $M$, the notation $\langle M \rangle$ denotes an encoding, ...
3
votes
2answers
118 views

Can a method be written if the language is undecidable?

If a language is decidable, we can write a method that always halts and returns true for each string that is an element of the language and ...
5
votes
0answers
87 views

Make a tag system simulate a finite automaton?

Tag systems are Turing-complete. I was wondering if there is any easy way to create tag systems that simulate finite automata. So create tag systems that recognize languages, e.g. by having at the end ...
1
vote
1answer
106 views

Is it possible to write a universal loop program for if-then & loop programs and it is possible to write a universal while program for while progra

Is it possible to write a universal loop program for if-then & loop programs and it is possible to write a universal while program for while programs? Long version and some background: Before ...
5
votes
2answers
128 views

Turing completeness

I encountered the brainfuck programming language which I know is turing complete. However I then decided to create a high level language that gets compiled to brainfuck code. There is only one data ...
3
votes
1answer
140 views

Natural RE undecidable problems but not Turing-complete

The Halting problem is a natural undecidable language which is complete for the set of recursivly enumrable sets. I am interested in undecidable but not Turing-complete language such that we can not ...
0
votes
3answers
134 views

Looking for some more details on “Turing” devices

I've been reading a lot of computer science literature in the recent past but haven't ran across an explanation of Turing machines, the different types, and why they seem to come up so often (I ...
0
votes
1answer
70 views

To prove Turing-completeness, is it enough to prove capability of producing arbitrary output?

Turing completness is being typically proved via reduction to already proved Turing-complete machine. Can the same be obtained by showing, that the machine in question is capable of generating ...
4
votes
1answer
1k views

How is the rule 110 Turing complete?

I've read the wikipedia page for rule 110 in cellular automata, and I more or less know how they work (a set of rules decides where to draw the next 1 or 0). I've just read they're Turing complete, ...
3
votes
3answers
253 views

What are the minimum requirements for a language to be considered Turing Complete? [duplicate]

Possible Duplicate: Are there minimum criteria for a programming language being Turing complete? I overheard a conversation on the topic and the conclusion that one gent came to was that in ...
6
votes
4answers
305 views

Is a device with restrictive execution policies Turing-complete?

There are devices that do not allow users to load any application they want on it, only run a limited class of applications approved by the device vendor. Take an iPhone as an example where new ...
10
votes
2answers
307 views

Do Higher Order Functions provide more power to Functional Programming?

I've asked a similar question on cstheory.SE. According to this answer on Stackoverflow there is an algorithm that on a non-lazy pure functional programming language has an $\Omega(n \log n)$ ...
12
votes
4answers
573 views

What is required for universal analogue computation?

What operations need to be performed in order to do any arbitrary analogue computation? Would addition, subtraction, multiplication and division be sufficient? Also, does anyone know exactly what ...
28
votes
6answers
3k views

Are there minimum criteria for a programming language being Turing complete?

Does there exist a set of programming language constructs in a programming language in order for it to be considered Turing Complete? From what I can tell from wikipedia, the language needs to ...
10
votes
2answers
2k views

Universality of the Toffoli gate

Regarding the quantum Toffoli gate: is it classicaly universal, and if so, why? is it quantumly universal, and why?