The tag has no wiki summary.

learn more… | top users | synonyms

4
votes
3answers
381 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
248 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
40 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
95 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
43 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
90 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
136 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
91 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 ...
4
votes
1answer
123 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 ...
7
votes
1answer
537 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 ...
6
votes
1answer
179 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
76 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 ...
0
votes
1answer
143 views

Right moving turing machine

I am interested in simulating any turing machine with a turing machine that is allowed only to move right. I guess that it should be pretty standard material and likely it is trivial (or known to be ...
5
votes
0answers
69 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
80 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
139 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
366 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 ...
0
votes
0answers
61 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
428 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
155 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
111 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
72 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
65 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 ...
3
votes
2answers
83 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
119 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
126 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
65 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
804 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
192 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
260 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
280 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)$ ...
8
votes
3answers
355 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 ...
19
votes
5answers
2k 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 ...
9
votes
2answers
956 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?