The tag has no usage guidance.

learn more… | top users | synonyms

1
vote
1answer
88 views

Is the system of measuring length in the US is Turing complete?

The author here writes: Little known fact, the system of measuring length in the US is Turing complete My question is: Is the system of measuring length in the US is Turing complete?
0
votes
0answers
42 views

Does Turing Completeness imply the existence of a Universal Program?

Please correct me if at any time my definitions are wrong. Suppose we have a programming language $L$ over some set $D$ with semantic (partial) n-ary functions $\varphi^n:D \to (D^n \to D)$. Assume $L ...
4
votes
0answers
31 views

Why does using an encoding trick like Gödel numbers make a register machine universal?

Here the author describes the Random Access Stored Program machine and the problem of indirect addressing. The author states: But this does not solve the problem (unless one resorts to Gödel ...
1
vote
2answers
87 views

Can one consider living (biological) cell to be Turing Complete?

Universal Turing Machine can be boiled down to two components. Infinite tape of input and an action table, a finite state machine that moves read/write head along the tape and writes to it depending ...
0
votes
0answers
23 views

Turing-Complete Supervised Learning Algorithms

I'm trying to decide on what algorithm I should use for my machine learning project. I need Turing-completeness. What supervised learning algorithms are Turing-complete? Of those, what are the best? ...
3
votes
2answers
60 views

Are Random Forests Turing-Complete?

Is the random forests algorithm Turing-complete? As in, can any algorithm be represented by a given "tree" in the forest?
5
votes
1answer
409 views

Is something more than Turing complete Turing complete?

In complexity theory, we do not call a decision problem that is not in NP "NP-complete". But in computability, do we call a machine model "Turing complete" if it can compute functions which Turing ...
1
vote
2answers
45 views

Non Recursively Enumerable Languages

Can someone give me an example of Non Recursively Enumerable language... i.e. A language which no Turing machine can accept ? What makes a language non recursively enumerable ?
6
votes
4answers
266 views

Is the halting problem always decidable for non-universal programs?

For every non-universal computable program $P$ that takes input of type $D$ does there exist some total computable function $g$ that takes an input $I$ of type $D$ and decides successfully whether $P$ ...
0
votes
1answer
44 views

Given a λ-term, can I decide which machine model I need to express it?

I am having a hard time figuring out the specific relationship, of various things in computability. So we have a hierarchy of machines, with a (real life) upper bound of Turing machines, moving on ...
2
votes
0answers
33 views

What language features would I need to remove from a real programming language to make it decidable? [closed]

Let's say that I want to restrict certain features of a common programming language--for instance, C--such that the result is decidable, and thus no longer Turing-complete. What language features, at ...
1
vote
1answer
69 views

Explanation for indirect addressing

While reading about minimal instruction set computer I found out that one needs at least (for example) the ability to increment or decrement the value stored in register, a test for zero and a jump. ...
10
votes
1answer
219 views

Connection between NAND gates and Turing completeness

I know that NAND gates can be used to create circuits that implement every truth table, and modern computers are built up of NAND gates. What is the theoretical link between NAND gates and Turing ...
5
votes
0answers
102 views

Computational power of Actor Model

In the question below, let TM be Turing machine, NTM be nondeterministic Turing machine and PTM be probabilistic Turing machine. In his paper "Actor Model of Computation: Scalable Robust Information ...
1
vote
0answers
22 views

What is a proof of normalization of Motte?

It is said that any term on the calculus of construction halts. I am studying it through Morte, which is a bare bone implementation of the coc available on github. Is there any simple proof of ...
5
votes
1answer
170 views

How rule 110 would be proven to be universal if the tag system did not exist?

I was reading about Cellular Automata and I read in this question that Matthew Cook proved that rule 110 is universal, and that his proof relied upon showing how rule 110 can simulate a tag system. ...
5
votes
3answers
904 views

Is there an algorithm for converting Turing machines into equivalent Lambda expressions?

We know that Turing machines and Lambda Calculus are equivalent in power. And There are proofs for that, I'm sure. But is there an algorithm, a systematic way for us to convert a Turing machine into ...
2
votes
2answers
89 views

Which calculus is based on first-order functions and is Turing complete?

Which calculus is based on first-order functions and is Turing complete? I know of calculi which are Turing complete, but based on higher-order functions: Lambda calculus SKI combinator calculus ...
15
votes
1answer
351 views

Does a do-while loop suffice for Turing-completeness?

I know that, in imperative programming languages, a while-do loop is sufficient as a control flow construct to make the language Turing-complete (as far as control flow goes - of course we also need ...
5
votes
5answers
596 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 ...
5
votes
1answer
160 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?
16
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
34 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
74 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 ...
8
votes
1answer
286 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 ...
5
votes
1answer
128 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
728 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: ...
6
votes
2answers
391 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
53 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
185 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 ...
20
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
72 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
209 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
84 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 ...
13
votes
1answer
164 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
530 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 ...
6
votes
1answer
418 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
48 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 , ...
5
votes
2answers
438 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 ...
1
vote
0answers
172 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
146 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
176 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
203 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
329 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 ...
10
votes
1answer
739 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
990 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
161 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
111 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 ...
3
votes
1answer
209 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 ...