Questions tagged [turing-machines]

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

Filter by
Sorted by
Tagged with
0 votes
1 answer
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 ...
user avatar
0 votes
0 answers
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 𝑣}
user avatar
  • 1
1 vote
1 answer
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 ...
user avatar
2 votes
1 answer
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 ...
user avatar
1 vote
1 answer
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 ...
user avatar
-1 votes
0 answers
40 views

How do I prove $\leq_{T}$ is a symmetric relationship on $P(\Sigma^*)$

Does a reflexive and transitive Turing reducible relation on the powerset of all strings imply symmetry, too? Here is my understanding. If $\leq_{T}$ is transitive on $P(\Sigma^{*})$, then given $A \...
user avatar
0 votes
0 answers
46 views

What is the purpose of a witness in existential projection?

I am reading my class notes and have come across the following terms - The existential projection of a language $B \subseteq \Sigma^{*}$ is the language, $\exists B \subseteq \Sigma^*$ defined by $\...
user avatar
3 votes
1 answer
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 ...
user avatar
0 votes
1 answer
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.
user avatar
2 votes
0 answers
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 ...
user avatar
3 votes
0 answers
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 ...
user avatar
3 votes
2 answers
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 ...
user avatar
0 votes
1 answer
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 ...
user avatar
0 votes
0 answers
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 ...
user avatar
  • 1,257
1 vote
1 answer
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?
user avatar
  • 11
1 vote
1 answer
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 ...
user avatar
0 votes
0 answers
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 ...
user avatar
1 vote
1 answer
53 views

What is the relationship between Kolmogorov Complexity and Turing Machines?

I am trying to understand the following definition - 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(\...
user avatar
0 votes
0 answers
14 views

Turing machine configuration in first order logic

In class we were trying to solve the following problem on Carnap: Suppose we start M on input w = 0. What is the description C(M, w, 1) of the configuration after one step? I know the answer might be ...
user avatar
  • 1
0 votes
1 answer
38 views

Is it possible for a programme to return an output with more entropy than the entropy of the programme's code itself?

Suppose that $P$ is a random variable that takes values in the space of computer programmes. So, basically, $P$ is some code (e.g. C, Python, or some theoretical one like the one used in the tapes of ...
user avatar
  • 385
5 votes
2 answers
506 views

How does this definition of a computable function work?

I have the definitions of computable (from my class notes) over here: $f$ is computable if there is a computable function $\hat{f}:\Bbb N \times \Bbb N \to \Bbb Q$ such that, for all $n,r \in \Bbb N$ ...
user avatar
-3 votes
1 answer
21 views

Two-tape deterministic Turing machine input block [closed]

I was working through a textbook and got stuck on a question. The Main tape contains a non-empty block of as and bs (representing a word w) "In the case where the input block on the Main tape ...
user avatar
0 votes
0 answers
25 views

If you go to far left/right in a tape, will there come a blank?

Under you will see a turing machine that accepts strings with equal numbers of 0s and 1s. I have been told that the machine will be stuck at q3 just moving left and will never move right since it will ...
user avatar
  • 143
0 votes
0 answers
63 views

Are there any statements that are n-undecidable for all n?

I understand that in a sufficiently complicated, consistent formal system, not all statements are true, not all statements are decidable, not all statements' decidability is decidable, 3-decidable, ......
user avatar
  • 1,230
1 vote
1 answer
42 views

Turing machine, alphabet: $\{0,1\}$, accepts any word $w$, and on the tape the word $w$ is written followed by $0$-s as the number of the $1$-s in $w$

So I just started studying Introduction to the Theory of Computation (I'm a student for Computer Science, this is the first week of the course), and I've got some exercises, which are only for myself (...
user avatar
3 votes
0 answers
45 views

Is it possible to have a Turing-complete language that can't possibly go into an infinite loop?

Does there exist a Turing-complete system that can never be programmed to go into an infinite loop? For all I know about Turing machines, this should not be possible. An arbitrary Turing machine can ...
user avatar
3 votes
0 answers
56 views

Would a proof-search for a contradiction halt in non-standard models of PA arithmetic?

I recently came across the following claim in Eliezer Yudkowsky's post about the limits of first-order logic β€œ Suppose I build a Turing machine that looks for proofs of a contradiction from first-...
user avatar
0 votes
0 answers
65 views

How are results involving Turing machines subsumed by ZFC set theory?

In order to talk about computability and computational complexity theory, you need a model of computation, and we usually take Turing machines as theoretical models for this. I am wondering how both ...
user avatar
0 votes
1 answer
56 views

Universal property of Turing machine

The Church-Turing thesis states that the computation ability of Turing machine is stronger or equal to any "computability model" (whatever that means) we can come up with. Are we able to ...
user avatar
0 votes
1 answer
71 views

Computability (Cutland) vs. Computability, Complexity and Languages (Davis et al.)

I had basic introduction to computability theory via Turing machines with some, rather basic, results. My background is a mixture of an undergraduate level math and cs. Now, I am looking for something ...
user avatar
  • 1
0 votes
0 answers
28 views

Circular Rotation Plate with Guides and Drive

I have an interesting machine which performs flawlessly. I've successfully reverse engineered the machine's motion using motion simulation software (SW). But I was only able to closely duplicate the ...
user avatar
  • 101
0 votes
0 answers
31 views

1. Given a Turing Machine T , are there any input strings on which T loops forever? 2. Given a Turing Machine T and a string w, does T reject input w?

Given a Turing Machine T , are there any input strings on which T loops forever? Given a Turing Machine T and a string w, does T reject input w? How to prove the above two question's decidabiltiy , I ...
user avatar
0 votes
0 answers
32 views

Proof that the halting set is recursively enumerable using Dovetailing

I am trying to understand how the halting set 𝐾:={(𝑖,π‘₯)∣ program 𝑖 halts when run on input π‘₯} is recursively enumerable i.e. Turing machines that halt on a blank tape form a recursively ...
user avatar
0 votes
2 answers
46 views

Intuitve Proof that the halting set is recursively enumerable

I am trying to understand intuitively how the halting set $K := \{(i, x) \mid$ program $i$ halts when run on input $x\}$ is recursively enumerable. Is there a simple explanation which says why this is?...
user avatar
0 votes
0 answers
20 views

Is self-reference required to show the halting problem is undecidable?

The common proof of the undecidability of the halting problem using a hypothesized halting-decider HALTS and constructs a pathological Turing machine $M$ that halts on a string $w$ exactly when HALTS($...
user avatar
  • 1
0 votes
1 answer
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 ...
user avatar
1 vote
0 answers
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 ...
user avatar
  • 21
2 votes
1 answer
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 ...
user avatar
  • 70
2 votes
1 answer
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 ...
user avatar
0 votes
0 answers
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.$
user avatar
3 votes
1 answer
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 ...
user avatar
  • 78.4k
0 votes
0 answers
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!
user avatar
  • 113
0 votes
0 answers
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 ...
user avatar
  • 339
2 votes
0 answers
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 ...
user avatar
  • 121
0 votes
0 answers
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 ...
user avatar
  • 1
3 votes
1 answer
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 ...
user avatar
3 votes
1 answer
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 ...
user avatar
0 votes
1 answer
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 = &...
user avatar
0 votes
0 answers
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 ...
user avatar
  • 29
0 votes
0 answers
63 views

Show that the collection of Turing-recognizable languages is closed under union

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$,...
user avatar

1
2 3 4 5
…
18