# Questions tagged [turing-machines]

This tag is suited for questions involving Turing machines. Not to be confused with finite state machines and finite automata.

872 questions
Filter by
Sorted by
Tagged with
32 views

### Halting problem reduction, what am i doing wrong

I have the following problem. Prove that $L_1=\{\langle M\rangle| \exists w \in \Sigma^*: M(w)\downarrow\}$ is undecidable (where $M(w) \downarrow$ means M halts on input w). I have come up with this ...
21 views

### Difficulty understanding a 1-tape TM program which solves and includes time analysis of the program [closed]

I need to sketch a 1-tape TM program which solves and also includes a time analysis of the program, e.g. 𝑂(𝑛), 𝑂(𝑛𝑙og 𝑛), 𝑂(𝑛3), etc.; 𝐿 = {𝑢#𝑣: 𝑢, 𝑣 ∈ {0,1}∗ and 𝑢 is a substring of 𝑣}
1 vote
37 views

### Turing Machines independent of ZFC

We can construct a Turing Machine M whose behavior is independent of ZFC by making it look for a contradiction in ZFC. But I also know that if any Turing Machine does in fact halt, it can always be ...
57 views

### Is there some kind of equivalence between Turing Machines and a formal system of axioms?

I know that the set of provable propositions in a sufficiently complex formal system is recursively enumerable but non-recursive, and so no Turing Machine could decide all the propositions that could ...
1 vote
72 views

### Is the set of Turing Machines decidable in ZFC non-recursive?

Let S be the set of all the TMs which halting is decidable in ZFC (for each TM in S, we can find one algorithm in ZFC that determines whether the machine halts or not). Is S recursive? Is there one ...
40 views

86 views

### Why is the post correspondence problem undecidable?

The post correspondence problem is, to my understanding, given two ordered collections of strings with the same cardinality, i.e., $\{t_1, t_2, \dots, t_n\}$ and $\{w_1, w_2, \dots, w_n\}$, does there ...
49 views

### Countability of computable real numbers [closed]

Is the set of all real numbers whose decimal expansions are computed by a machine not countable? Assume a digital machine not capable of computing infinite decimal places.
102 views

### Is there a particular Turing Machine which halting is undecidable in all formal systems?

Hanf and Myers showed in 1974 that there exists a single set of tiles that will tile the plane only in a non-computable way. How are we to interpret this? Does it imply that there is a particular ...
32 views

### HexLife: Turing complete?

Has anything "interesting" been discovered if one generalizes Conway's Life on a rectangular grid to a hexagonal grid? There have been several explorations of Life on a hexagonal grid. In ...
63 views

### What does it mean for a language to be sparse?

A language $A \subseteq \sum^{*}$ is sparse, and we write $A \in SPARSE$, if there is a polynomial q such that, for all $n \in N$, $$\left|A \cap \sum^{n}\right|\leq q(n)$$ The definition of a ...
205 views

### Prove that there's no decidable language that separates two other languages.

I was reviewing for an exam and I found this question: Let A and B be two disjoint languages (that is, A ∩ B = ∅). Say that a language C separates A and B iff A ⊆ C and B ⊆ (not C) . Define two ... 14 views

### Definition of a time-complexity of a function $f:A\to B$

Let $f:A\to B$ be a function where $A$ and $B$ are at most countable sets. The bijections $\mathbb N\to A$ or $\mathbb N\to B$ are not unique, and I only know the time-complexity definitions for ...
1 vote
64 views

### If NL = P, prove that P!=PSPACE

If NL = P, how do we prove that P != PSPACE? Do we have to use Savitch's theorem?
1 vote
41 views

### What does an optimal Turing Machine mean?

Let $M$ be a TM, and let $x \in \sum^*$. The plain Kolmogorov complexity of x with respect to m is - $C_{M}(x) = min\{|\pi|:\pi \in \sum^* \land M(\pi) = x \}$ A TM U is optimal if, for all TM M there ...
19 views

### How to prove a turing machine is decidable which accepts ⟨A, B⟩ | A and B are NFAs and L(A) ⊆ L(B).

So I'm trying to construct a Turing machine M = = {⟨A, B⟩ | A and B are NFAs and L(A) ⊆ L(B)}. I was wondering how to approach this problem as there are total 4 possibilities - A accepts A B accepts ...
1 vote
53 views

31 views

### turing-reduction Proof: $A = \{(u,v) | T(M_u) \subseteq T(M_v)\}$ by showing $H_0 \leq A$

i have a hard time understand turing-reductions. This is my first exercise without a solution and I don't know wheter this is the proper solution. (The only thing i know for sure is, that A is indeed ...
1 vote
31 views

### How is Kolmogorov complexity calculated?

In lectures, my professor discussed Kolmogorov complexity for 10 minutes but I have too many questions opened. My professor claimed (and I was able to prove it myself) that $|K(X)| \leq |x|+1$. But ...
100 views

### Running an infinite amount of Turing Machine steps in a finite amount of time: What consequences?

If we had some sort of black box that allows us to run an infinite amount of steps of a Turing machine in a finite amount of time (no limitation on the length of the tape), and be able to output ...
73 views

### How to show that if there's a mapping reduction from L to its complement, it doesn't imply that L∈R?

I have the following prove/disprove claim: if $$L\leq_m L^{c}$$ then $$L\in R$$ I figured out that I can theoretically provide a counter-example where both $$L,L^{c}\not\in(RE\cup co-RE)$$ but ...
26 views

### About Turing machine. what is Turing machine of $\lfloor n/2\rfloor$?

Now I can not even start what to do.. Im wondering What is Turing machine of $\lfloor n/2\rfloor$ = the greteat integer $\leq n/2.$
109 views

### Lower bound for $bb(7)$ - which one is true ? And what is the bound for $bb(6,3)$?

$bb(7)$ is already extremely large , but I found a discrepancy in the lower bound: In this survey the lower bound for $bb(7)$ is given as $$BB(7) > 10^{10^{10^{10^7}}},$$ hence four tens in the ...
27 views

### Determine L(M), the language recognized by M.

Below is provided a nondeterministic Turing machine. Could anyone explain to me how can I determine the language that is recognized by it? Thanks a lot!
47 views

### Can mathematical theories be infinitly complex?

I came across an intriguing interview conducted by Robert Kuhn who interviewed Gregory Chaitin, a mathematician at IBM. To pose my question upfront: Are his views accepted in the math community as ...
59 views

### Using diagonalization approach, how to show the existence of at least one set of natural numbers that is not computable?

I have studied the halting problem and the concepts of decidability and computability, however, I am stuck with the transfer of Turing machines to sets of natural numbers. Specifically, using the ...
74 views

### Multitape Turing Machine - Check input's primality

I've got this homework for next tomorrow and unfortunatelly I have no idea how to design this machine. Requirement: Build a 2-tapes Turing Machine, which has a number as input a natural number (unary ...
110 views

### Proof that the Post Correspondence Problem is undecidable

The lecture of MIT professor Michael Sipser, available here and his book Introduction to the Theory of Computation, Third Edition, chapter 5, both contain essentially the same proof that there can be ...
83 views

### Are there countably many symbols (in the context of computation theory)?

I've seen this kind of argument on countability of Turing-recognizable languages in several places: For any Turing machine $M$ consider it's encoding into a string $\langle M \rangle$. This encoding ...
30 views

### Group input string by 4 characters by adding " " with a Turing Machine

I have this problem, where I have an input where: alphabet of the input string is Σ = {a,b,c} need to add a " " after every 4 characters. Example: Input = "aabacc", Output = &...
Sipser's Introduction to the Theory of Computation, Third Edition, Chapter 3, Problem 3.16A asks us to prove this and offers the following solution: 'For any two recognizable languages $L_1$ and $L_2$,...