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
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 ...
- 1
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 π£}
- 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 ...
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 ...
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 ...
-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 \...
- 239
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
$\...
- 239
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 ...
- 6,540
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.
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 ...
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 ...
- 29.3k
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 ...
- 239
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 ...
user1052197
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 ...
- 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?
- 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 ...
- 239
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 ...
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(\...
- 239
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 ...
- 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 ...
- 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$
...
- 239
-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 ...
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 ...
- 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, ......
- 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 (...
- 47
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 ...
- 131
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-...
- 305
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 ...
- 1,924
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 ...
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 ...
- 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 ...
- 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 ...
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 ...
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?...
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($...
- 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 ...
- 11
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 ...
- 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 ...
- 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 ...
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.$
- 21
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 ...
- 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!
- 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 ...
- 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 ...
- 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 ...
- 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 ...
- 396
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 ...
- 580
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 = &...
- 25
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 ...
- 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$,...
- 396