Questions tagged [turing-completeness]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
0
votes
2answers
90 views

How can a 64KiB computer do the same task as a modern computer?

I took an extremely interesting intro to CE course, learning about transistors/memory/logic gates up to LC-3 assembly. Something that was really interesting to me was learning about how a processor's ...
26
votes
7answers
7k views

Are all turing complete languages interchangeable

Note, while I know how to program, I'm quite a beginner at CS theory. According to this answer Turing completeness is an abstract concept of computability. If a language is Turing complete, then ...
1
vote
1answer
43 views

How to compute (x MOD y) with just SUM and MULT gates?

It is known that $\{ SUM, MULT \}$ is Turing-complete, i.e. every Turing machine has an equivalent circuit made up of $SUM$ and $MULT$ gates. By the way, I could not come up with designing $MOD$ ...
0
votes
0answers
30 views

Is it possible to have a code which cannot be solved by computer

I was looking at Turing machines and Turing completeness and I was wondering whether it is possible to prove that there is a problem which cannot be solved by a Turing complete computer or whether it ...
1
vote
1answer
58 views

Emergent complexity and Turing Completeness

Is there some link between the concept of emergence and Turing Completeness? The ideas feel intuitively like they might be linked, but I can find nothing online. The idea came to me because I was ...
2
votes
0answers
51 views

In what sense can a cellular automaton be Turing complete? [duplicate]

The rule 110 cellular automaton is known (or claimed) to be Turing complete. But what exactly does it mean? I do know what Turing completeness mean. Roughly speaking a language is Turing complete if ...
2
votes
1answer
267 views

Infinite Boolean circuits as a model of computation

Boolean circuits are non-uniform models of computation in that they require a different circuit for each length of input. The typical way of uniformizing a family of Boolean circuits is to define a ...
8
votes
1answer
11k views

How is PowerPoint Turing complete?

From my understanding, Turing complete means that the program or machine can complete any computation that a Turing machine can complete, which to me means any computation. So how can something like ...
43
votes
9answers
15k views

Why are some programming languages Turing complete but lack some abilities of other languages?

I came across an odd problem when writing an interpreter that (should) hooks to external programs/functions: Functions in 'C' and 'C++' can't hook variadic functions, e.g. I can't make a function that ...
1
vote
1answer
585 views

What was the first Turing-Complete programming language?

What was the first turing-complete language? Know about the first machines and computers, but not the programming language.
10
votes
1answer
233 views

Is there a dual concept to “Turing Complete” in logic?

Two computing models can be shown to be co complete if each can encode a universal simulator for the other. Two logics can be shown to be co complete if an encoding of the rules of inferences (and ...
3
votes
1answer
158 views

Who was the first to show that there is a Universal Turing-Machine that uses a binary alphabet?

The title says it all, I think. We know there are universal Turing-machines that only use a binary alphabet. But who proved this first? Turing himself showed the existence of a universal Turing ...
1
vote
3answers
275 views

Is the ability to do depth first search a proof of Turing Completeness? Can we write a non-TC automaton that does DFS?

As the title states. Let's say we have a set of inputs that define a tree structure. Is it possible to construct an automaton that can perform depth-first search on this data that is not Turing-...
4
votes
1answer
1k views

Turing-completeness, Conway's Game of Life and Logical Gates

I was recently given an assignment at university asking me to discuss the universal computational capability of Conway's Game of Life. I'm not required to actually build up a Universal Turing machine ...
1
vote
1answer
94 views

Is there a problem solution which, if implementable in a given language, implies that that language is Turing complete?

I have been researching a bit lately and found myself thinking about the title question for some time now, but have found nothing conclusive. For example, some problems require loops practically - ...
1
vote
0answers
41 views

What portion of all possible turing machines halt?

Has anyone estimated Chaitin's constant for Turing machines with an empty tape as input?
4
votes
0answers
129 views

Is a reduced Wang B-machine Turing-complete?

A Wang B-machine has only 4 instructions: right: Move tape head right left: Move tape head left ...
0
votes
1answer
210 views

Find the odd shortest path is NL

OddPath be a set of all G, s, t, such that G is a directed graph with a path from node s to node t, and the shortest such path has odd number of edges. How can I show OddPath is NL? I think about it ...
4
votes
1answer
280 views

Lambda Calculus in Rewriting systems

How to do or implement Lambda Calculus in a Rewriting systems? Rewriting systems are Turing complete. But I can't figure out how to do lambda calculus or functions with them.
1
vote
1answer
246 views

How many gates until Turing Complete

A computer can be pretty much made using just nand gates and a clock. Suppose you randomly place down nand gates on a board and connect them randomly to other nand gates. How many gates does someone ...
12
votes
1answer
1k 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 ...
34
votes
5answers
14k views

What does being Turing complete mean?

I see that most definitions of what it is to be Turing-complete are tautological to a degree. For example if you Google "what does being Turing complete mean", you get: A computer is Turing ...
6
votes
2answers
1k views

Looping and branching with Algorithmic Differentiation

Algorithmic (aka Automatic) Differentiation is a wonderful technique for numerical computation of derivatives. I understand how it relates to the fact that we know how to deal with every elementary ...
1
vote
1answer
72 views

Is learned RNN still universal?

I know it has been shown that RNNs are Turing complete. So for any Turing machine, there exists a configuration of a RNN that is equivalent to it. But I'm wondering, is all those configuration ...
20
votes
2answers
7k 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, ...
5
votes
1answer
543 views

Confused between turing-completeness and universal approximation - are they related?

I am trying to de-knot a point of confusion in my mind regarding "turing-completeness" and the "universal approximation theorem". The context here is deep neural nets: So, consider two types of ...
2
votes
1answer
1k views

Why is the video game Braid Turing-complete?

It's written in wikipedia https://en.wikipedia.org/wiki/Turing_completeness#Games that the video game Braid is Turing-complete. I've played Braid before but I can hardly reconcile it with Turing ...
2
votes
1answer
77 views

How does universal calculator work?

As I understand, the concept 'computation' started dependent on hardware (like looms for instance). The Hardware defines (physical cascades) what happens between input and output. I think I saw in ...
3
votes
2answers
67 views

Trying to figure out if a modern computer is capable of manipulating arbitrarily large pointers

I was just thinking about Turing-completeness and its relationship with modern computers. I've always thought that a real computer is not technically Turing-complete. It is equivalent to a linear-...
15
votes
2answers
4k 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 ...
0
votes
1answer
39 views

Characterisation of Turing completeness? [duplicate]

I know the definition of a Turing machine but I am trying to find a practical way to characterize a Turing-complete language. For example, an imperative language is Turing complete if it has ...
1
vote
1answer
261 views

Is Functional Complete means Turing Complete?

I noticed that AND, OR, NOT those three logic gates are Functionally Complete, it means I can represent any trues table only by those three gates. A Turing machine may halt or not in a particular ...
6
votes
2answers
2k views

Is there a way to test “Turing completeness”?

I asked my algorithms teacher today the very same question that is stated in the title, but he seemed a bit unsure, either on the question or on the concept, so I thought I'd try here too. Is there a ...
0
votes
2answers
60 views

Is a physical process with unbounded input Turing equivalent?

Church-Turing thesis states that any effectively computable process is computable by a TM. Let's assume for now that it means that every physical machine is computable by a TM. Let's call it A. Now ...
3
votes
1answer
213 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 ...
12
votes
3answers
2k views

Can every self-modifying algorithm be modelled by a non-selfmodifying algorithm?

If we have any arbitrary computer program that can modify its instructions, is it possible to simulate that program with a program that cannot modify its instructions? Edit: I am new to ...
3
votes
1answer
90 views

What is a proof of normalization of Morte?

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

Why are functional languages 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 ...
3
votes
1answer
6k views

Can the human brain be considered Turing complete? [duplicate]

I'm not a student in computer science, but from what I understand from the Wikipedia article on the topic, a programming language is Turing complete if it can emulate another Turing complete language'...
0
votes
1answer
82 views

Turing Completeness of System Which Randomly Fails to Complete Calculations

If one were to create a variant of a turing complete language which upon completing a calculation randomly changes the answer by one, would it be Turing complete? For example, say I had a Python ...
4
votes
1answer
499 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 ...
0
votes
0answers
126 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 ...
3
votes
0answers
97 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 ...
4
votes
2answers
1k 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 ...
2
votes
2answers
196 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?
0
votes
0answers
63 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? ...
5
votes
1answer
842 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, ...
5
votes
1answer
933 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 ...
6
votes
4answers
556 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$ ...
4
votes
2answers
6k 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 ?