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
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 ...
• 6,540
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 ...
• 29.3k
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,257
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?
• 11
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 ...
• 11
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 ...
• 21
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 ...
• 70
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 ...
• 78.4k
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!
• 113
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 ...
• 339
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 ...
• 121
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 ...
• 396
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 ...
• 580
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 = &...
28 views

Are machines with a finite set of states under a finite alphabet turing-equivalent?

Are TMs where |Q| < 2021 and |Ξ| < 2021 (Q is the set of states and Ξ is the tapeβs alphabet) turing-equivalent ? By Turing equivalence I mean that two computers P and Q are called equivalent if ...
• 29
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$,...