Questions tagged [turing-machines]
This tag is suited for questions involving Turing machines. Not to be confused with finite state machines and finite automata.
906
questions
0
votes
0
answers
14
views
Simulation DFA on turing machine
We will encode all element of M - Deterministic Finite Automata and w in unary numbers.
For example
We will encode all element of M and w in unary numbers.
Q = {q2, q5, q9}
The first element of Q is ...
0
votes
0
answers
25
views
turing machine show equivalence
I have a question regarding proofs to show the equivalence of different turing machines and their possible time and space overhead:
I have to show, that a usual deterministic turing machine is ...
- 19
2
votes
0
answers
35
views
What is the exact difference that makes Chaitin's number uncomputable while this other number (from another post) computable?
This is a follow-up to this post. In the post, the user defines a number $x$ that is $1$ if $\textsf{ZFC}$ is inconsistent and $0$ otherwise. By virtue of the fact that $x$ is either $0$ or $1$, it is ...
- 2,297
0
votes
0
answers
48
views
which notion of provability in Turing's paper 1936?
In Turing's article 1936 https://www.cs.virginia.edu/~robins/Turing_Paper_1936.pdf
Turing provides a proof in §11 p.259 for the Hilbert decision problem "Entscheidungsproblem".
p. 259 he ...
- 169
1
vote
0
answers
13
views
Proving the language 2-SIMPLE-PATH is in NL
The Question
I define the language$$\mathsf{2-SIMPLE-PATH}=\left\{ \left\langle G,s,t\right\rangle \left|\begin{array}{c}
\mathsf{there\;are\;two\;different}\\
\mathsf{simple\;paths\;from}\;s\;\...
- 242
1
vote
0
answers
21
views
What does it mean for a language L to be recognisable in polynomial time?
Does it mean there exists a TM which decides L in polynomial time - that is, for any input w, the TM decides in time polynomial in the input whether w belongs to L or not - or is it rather just that, ...
0
votes
1
answer
18
views
Proving a function is primitive recursive using nonatomic functions
When proving that f is primitive recursive can we use functions that are proven to be primitive recursive like q(x,y)=x/y and other nonaxiomatic functions?
0
votes
0
answers
51
views
Does every state in all Turing-complete computational models have infinitely many potential ancestor states?
By 'state', I mean a full snapshot of the system, sufficient that you could continue computing from that point. E.g. for a universal Turing machine, this would be a description of the rules, the ...
- 5,514
0
votes
1
answer
76
views
It is possible to show ($HALT_{TM}$ is decidable $\Rightarrow A_{TM}$ is decidable), but how about the converse?
Let $HALT_{TM} = \{ \langle M , w \rangle : M \text{ is a TM and } M \text{ halts on } w \}$ and $A_{TM} = \{ \langle M , w \rangle : M \text{ is a TM and } M \text{ accepts } w \}$.
It is possible to ...
- 1,871
1
vote
0
answers
24
views
Language of all graphs that have diameter larger than $\frac{n}{2}$
Let $$A=\{\langle G\rangle \mid G=(V,E) \text{ is an undirected graph, } |V|=n \text{ and } \text{diam}(G)\geq n/2\}$$
Show that $A\in NL$ by showing a log space decider.
I've tried to create a ...
- 23
0
votes
0
answers
27
views
Is there a lower bound on the rate of growth of distinct algorithms (vs. description size) in a Turing-complete system?
...where a "distinct algorithm" is approximately defined as an algorithm that returns a value distinct from all others thus far.
I would think not, because you can always construct some ...
- 5,514
0
votes
0
answers
29
views
Turing machine problem.
I saw a problem of a Turing machine that seemed interesting to me, it is the following:
Construct a TM that decides if a given word has a even number of 0's and an odd number of 1's.
I wanted ...
- 533
0
votes
0
answers
47
views
Construct a TM that decides if a given word has a even number of 0's and an odd number of 1's.
I ask this again.
Construct a TM on the alphabet $Σ=\{0,1\}$ that decides if a given word has a even number of 0's and an odd number of 1's.
I don't have a preview because I really don't understand ...
- 765
0
votes
1
answer
33
views
Can you prove that the difference of these two undecidable sets is un/decidable?
I'm just an amateur programmer so please bear with me
consider the following sets of numbers
$$
D=\{m|\text{$m$ is a turing machine and does not halt on blank input}\}
$$
$$
G=\{m|\text{$m$ is a ...
- 111
2
votes
0
answers
87
views
Many-one reduction of $K^c$ to $A$ [closed]
I saw some examples of reduction one of them is this:
We say set $B$ is many-one reducible to $A$ if there exists a total cumputable fucntion $f$ that:$$x\in B \iff f(x) \in A$$
and we write $B\leq_m ...
- 21
2
votes
0
answers
58
views
Decidability of redundancy of axiom in classical propositional logic
Let $\mathcal{S}$ be a complete set of axioms for classical propositional logic (for example, say the Hilbert axioms), and let $\pi\in\mathcal{S}$ be an axiom in it. Is it decidable (in a Turing ...
- 1,224
0
votes
0
answers
9
views
Reduction of Context Free Grammar
I'm doing some problems about reductions of Context Free Grammar and I've some troubles with one of them. Here is the statement:
I tried using morphisms with other symbols with the objective of make ...
- 33
0
votes
1
answer
39
views
Can this language be decided in polynomial time?
Let $L=${$0^{2^n}|n>=0$}
Can this be decided in polynomial time?
I can decide it in non polynomial time, by going over all '0's and delete 2 of them from the beginning and the end of the string, ...
- 23
1
vote
0
answers
36
views
Proving that $P \subseteq NP,$ formally and using Turing Machines.
My question urges on proving that $P \subseteq NP.$ The definitions I am using follow below:
Definition. We define the set of languages $DTime$ as
$$ DTime(t(n)) = \{ L \colon \text{there is a ...
- 1,171
3
votes
0
answers
121
views
Using non-computable numbers to compute other non-computable numbers
We can define an equivalence class of irrational numbers based on whether two irrational numbers are rational multiples of one another. For example, given an irrational number $x$, we have the ...
2
votes
1
answer
100
views
If two Turing machines halt iff they find a proof that the other halts, does either of them necessarily halt?
This question was inspired by this excellent question on MathOverflow.
Assume that there are two Turing machines $M$ and $N$ that search through all ZFC proofs in some order, and if either of them ...
- 3,743
1
vote
0
answers
20
views
Turing Machine for $𝐿 = \{𝑎^n 𝑏^𝑚 c^{2^{nm}} : n,m\ge 1 \}$
This question requires high level description of Turing machine.
I found that we are able to solve a^n b^m c^nm by :
Step 1 : crossing out one a
Step 2 : continue to cross out one b followed by one ...
- 11
0
votes
0
answers
28
views
Decidability of the Membership problem
Good day!
I have the following question.
Given a subset S ⊆ N = {0, 1, 2...}, the S-Membership problem asks "Given a number n ∈ N, is n in S"?
We call the set S decidable iff its S-...
- 29
0
votes
0
answers
35
views
Turing-reducibility for guaranteed decider
The following exercise is taken from Theoretical Computer Science by Atiba.
Use Rice's theorem to demonstrate that every decidable language is Turing reducible to some language that is already ...
- 1
0
votes
1
answer
25
views
Can we prove that $L_1$ is decidable?
Let $L_1, L_2 \subseteq \Sigma^*$ be Turing recognizable languages. Suppose there is a computable function $f : \Sigma^* \to \Sigma^*$ such that $x \notin L_1 \to f(x) \in L_2$. Can we prove that $L_1$...
0
votes
0
answers
382
views
$L \subseteq \Sigma^*$ is decidable $\iff$ $I_L$ is computable
Let us denote $L \subseteq \Sigma^*$ a languague where $\Sigma$ is an alphabet. I want to show that
$$L \subseteq \Sigma^* \ is \ decidable \iff I_L \ is \ computable,$$
where $I_L$ is an indicator ...
- 71
2
votes
0
answers
61
views
Prove $NOTCONTEXTFREE_{TM}$ is not recursively enumerable?
$NOTCONTEXTFREE_{TM}$ = {$\langle M \rangle$, M is a turing machine and the language of M is not context-free}.
I'm trying to prove the language $NOTCONTEXTFREE_{TM}$ is not recursively enumerable. I'...
- 33
-3
votes
1
answer
142
views
An argument against the logic of the halting problem proof
Introduction
When reading a proof of the Halting Problem, something felt off with the way that the halting machine is fed into itself. It feels like there is an infinite chain of halting machines, and ...
- 103
4
votes
0
answers
89
views
Why do almost all points in the unit interval have Kolmogorov complexity 1?
I am reading
Jin-yi Cai, Juris Hartmanis, On Hausdorff and topological dimensions of the Kolmogorov complexity of the real line, Journal of Computer and System Sciences, Volume 49, Issue 3, December ...
- 961
1
vote
0
answers
60
views
Isn't this requirement true for any Turing machine?
I came across this proof today and I can't figure out what the second restriction is supposed to mean (marked in red) - does it mean, that for every Turing machine, that if it stops for an input after ...
0
votes
0
answers
19
views
Why would the Turing Machine constructed by the proof of Posts Theorem be computably enumerable?
Good evening,
I'm currently reading up about the Friedrich-Muchnik Theorem/Posts Theorem and will the construction makes sense, I can't really understand, why the construction would yield a computably ...
0
votes
0
answers
22
views
How can one decide this problem by using a halting-machine-oracle?
In the book I'm currently reading, there is the following set given:
While I understand the reasoning behind the argument given, I could not figure out how to actually construct the necessary ...
2
votes
0
answers
52
views
How can there be non-computably enumerable sets in a computably enumerable degree?
I was just reading up about turing degrees and the part marked in red confused me:
Screnshot of book page
If there was a non computably enumerable turing machine that could be computed given the ...
1
vote
1
answer
57
views
Formal definition of one Turing machine simulating another
Here on Wikipedia is says "In computer science, a universal Turing machine (UTM) is a Turing machine that can simulate an arbitrary Turing machine on arbitrary input". I would like to know ...
- 1,870
0
votes
0
answers
70
views
Proving that a language is Turing reducible to halt
I'm trying to complete the proof to show that language L is Turing reducible to HALT. Here is the problem:
Let $𝐿 = \{< M > | 𝐿(𝑀) = \{'X'\}\}$.
Prove that
$𝐿 \leq_T 𝐻𝐴𝐿𝑇$.
How would I ...
- 1
1
vote
0
answers
24
views
How to understand the transition function of Turing Machines?
I am going through a lecture on Turing Machines and am confused by the use of notations for the transition state function.
The transition function is defined as
$$ Q\times\sum \rightarrow (\sum \cup \{...
- 461
23
votes
2
answers
3k
views
How do uncomputable numbers relate to uncomputable functions?
All the online resources that I've seen on uncomputable numbers assume that they're all irrational. But this doesn't seem to be required by the definition. Wikipedia, for example, says that "[un]...
- 418
0
votes
0
answers
78
views
Turing-recognizable languages are closed under intersection
I know this has been asked and answered before in Stack Overflow. I'm trying to come up with my own proof but I seem to have one small problem.
Basically, we have to prove that if $L_1$ and $L_2$ are ...
- 1,035
1
vote
3
answers
61
views
Can every problem in Theory of Computation be stated as undecidable, by writing a reduction from Halting Problem?
Let us consider the problem that
Whether a given Turing Machine M, has at least 481 states.
Since the number of states of M can be read off from the encoding of M. We can build a Turing machine that, ...
2
votes
1
answer
60
views
Can the tape of a Turing machine be represented as a discrete function?
I'm just thinking aloud here, and to expand on this, each square of the tape could lie between integers, and discrete y values of the function could map to symbols. That way a given discrete/step ...
- 79
1
vote
1
answer
37
views
Is there a notion of an infinite "Rado graph-like" random algorithm?
Disclaimer before starting: I'm not using "algorithm" in the usual sense, but I don't know what the right term for what I'm talking about is, if there even is one. Here, "algorithms&...
- 82
2
votes
0
answers
45
views
Classifying a language into co-re using a Turing machine
I have the following language:
$$L=\{\langle M1\rangle,\langle M2\rangle: |L(M_1) ∩ L(M_2)|≤10 ~~\text{ or }~~ |L(M_1) ∩ L(M_2)|≥1000\}$$
I am told that this language is either r,re or co-re. it was ...
- 43
0
votes
0
answers
67
views
Understanding how a Turing-machine works
I'm reading chapter 7 of Sipser's Introduction to the Theory of Computation.
I'm in trouble understanding how the Turing-machine $M_2$ described at page 280 (third edition) works.
It's a Turing-...
- 803
3
votes
0
answers
44
views
Read head of a STANDARD Turing machine
In classes it has been explained to us that for a Turing machine to be standard it needs an infinite tape in both directions, a reading head and transitions, where the reading head can move to the ...
- 31
0
votes
0
answers
97
views
create a turing machine that decides the following language
I want to create a diagram of a turing machine that decides the following language.
$\{w \in $ $\{a,b\}^*: w = u^n, u \in \{a,b\}^+, n \geq 2\}$
The diagram I had planned to make was a very simple one,...
- 31
0
votes
0
answers
32
views
Exercise 12.11 of Rotman's an introduction to the theory of groups
I'm reading Rotman's an introduction to the theory of groups. I have a question about one of the exercises in Chapter 12 The Word Problem.
My attempt is:
Let $\{s_0, s_1, ..., s_m\}$ be the ...
- 623
0
votes
0
answers
24
views
In Godel's letter to von Neumann what is meaning of maxF?
This is probably basic. I am parsing Godel's letter to von Neumann and I am stuck in the following passage where he says "maxF"
One can obviously easily construct a Turing machine, which ...
- 101
7
votes
5
answers
565
views
Rigorous books on basic computability theory
Are there books on basic computability theory in which the authors formally prove computabiltiy of functions? By 'formal proof' I mean writing down explicitly the corresponding turing-machine, or ...
- 71
1
vote
0
answers
26
views
Limitations placed on an Oracle Turing Machine for Relativized Theorems
Are there any limitations that need to be placed on an oracle in order to maintain that the classical computability results (like the Halting Problem and the non-collapse of the arithmetic hierarchy) ...
- 749
0
votes
0
answers
14
views
Decidable Language For Encoded TM
For any random fixed word w inside the alphabet {0, 1}, given the language { <M> | M is a turing machine of alphabet {0, 1} that accepts w}, is this language ...
