# Questions tagged [turing-completeness]

The tag has no usage guidance.

215 questions
Filter by
Sorted by
Tagged with
29 views

### How can we test for Turing Completeness given any formal semantic specification?

I have seen the question asked many times always with the same answer: emulate a Turing machine on top of it. This seems like an ad hoc method so is there a more formal and general method to prove ...
1 vote
38 views

### Logarithmic space reduction from PATH to 2COLOR-PATH

2COLOR-PATH = {<G,s,t> | G is a 2-Colorable directed graph that has a directed path from s to t} I need to write a logarithmic space reduction from PATH to 2COLOR-PATH (explained above). I know ...
• 27
21 views

### 2-argument combinators and Turing completeness

SK, BCKW, and BAMT combinator systems are known to be Turing-complete and convertible into each other. (BAMT is mentioned in this blog post) ...
• 498
14 views

### How simple addition operation performed with just one instruction by BitBitJump?

According this: https://en.m.wikipedia.org/wiki/One-instruction_set_computer Its instruction has 3 operands, the meaning is: copy the bit addressed by a to the bit addressed by b and jump to the ...
1 vote
34 views

### What are the most minimalistic assembly's mnemonics to make complete turing machine?

Disclaimer: I'm a computer engineering student, not a computer science. Pardon me for mistakenly using computer science terms. I want to design computer architecture with the most minimalist design as ...
30 views

### Is it possible to use a non-Turing-complete language to describe the steps to build a Turing Machine?

First of all, it is impossible to use a Turing-incomplete language to simulate a Turing-complete one (see link) However, is it possible to use a Turing-incomplete language to describe the steps to ...
• 111
1 vote
18 views

### Structured program theorem w/o selection

The structured program theorem proofs Turing-completeness of structured programming, resp. of any programming language that includes sequences, selection (IF) and conditional loops (WHILE). I am ...
• 167
1 vote
70 views

### Constraints on the order of program semantics given by an enumeration of turing-complete system programs

There are Turing-complete systems like Jot where every natural number represents a valid program. This results in a Gödel numbering. Now, if the semantics of the programs were, say ...
• 191
74 views

### What is the name of the theory that says that Turing equivalence is universal, and Turing machines are maximally computationally powerful?

In the Chomsky hierarchy, level 0 grammars include all languages that can be recognized by a Turing machine. There is no level -1 (which would represent the class of languages that cannot be ...
129 views

### Is the Turing machine the only framework to analyse limits of computation?

In Theory of Computation lessons, the limits of computation are usually analyzed within the framework of Turing machines, so if something isn't solvable with Turing Machine, then we consider this ...
• 359
25 views

### Effectively universal Turing machines and Turing-completeness?

An effectively universal Turing machine $T$ is a Turing machine for which there exists a recursive reduction $f$ such that $\forall A:U(A)=T(f(A))$, where $A, f(A)$ are finite sequences of symbols (...
• 1,901
146 views

130 views

### is HaltingFuck computable?

A while ago I defined the language HaltingFuck, but I've never been able to figure out its computational class. The language is defined as follows: HaltingFuck is a language very much like Brainfuck, ...
• 417
1 vote
106 views

### Encoding Turing machine-like behavior using families of sequences of vector spaces and modules. P=NP related

Let $F$ be a field. Suppose we have a machine $T$ that works with words that are elements of $F$, for exmaple $F = \Bbb{Z}/2, \Bbb{Q}$ (using arbitrary precision arithmetic), or $\Bbb{Z}/p$ for a ...
• 538
80 views

• 91