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
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 ...
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\;\...
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 ...
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 ...
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 ...
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, ...
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-...
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'...
-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 ...
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 \{...
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]...
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-...
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 ...
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,...
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 ...
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 ...

1
2 3 4 5
19