Questions tagged [turing-machines]
This tag is suited for questions involving Turing machines. Not to be confused with finite state machines and finite automata.
703
questions
0
votes
0answers
10 views
Two tape turing machine for L = {a∗wwb∗ : w ∈{a,b}∗} without any bruteforce
I don't even know how to approach this problem. I was thinking to use two tape turing machine. First tape would be the input string and second tape for guessing w. And even if I have guessed w ...
0
votes
0answers
18 views
Rice theorem and trivial properties for decidability proof
I'm going to have a complexity theory exam and i understood the importance of Rice theorem in proving if given a language $L_{p}=(L|L\space satisfies\space the \space property\space\space p)$, is ...
0
votes
0answers
29 views
Regular Languages
i am stuck in this problem.
Prove that shuffle of 2 Context-free Languages is Recursive and Recursive-enumerable. Also prove that this new language is not necessarily Context-Free. I am able to do the ...
0
votes
0answers
14 views
Turing Equivalence counterexample
Given that A is Turing reducible to B, what would the set B need to look like such that B is not Turing reducible to A? I've been having a hard time with this idea and I would appreciate some examples ...
-2
votes
0answers
59 views
I'm stuck on this FLAT question, could someone help? [closed]
Let $\Sigma_1$ and $\Sigma_2$ be finite alphabets such that $Σ_1∩Σ_2=∅$. Let $L_1 \subseteq \Sigma_1^*$, $L_2 \subseteq \Sigma_2^*$ and define
$L \subseteq \Sigma^*$ as follows:
A string in $\Sigma^*...
1
vote
0answers
30 views
On the proof of the unsolvability of the word problem in semigroups
I'm trying to understand the following proof of the unsolvability of the word problem in semigroups. I tried to reproduce the proof from some kind of personal communication, so I'm not sure everything ...
0
votes
0answers
9 views
Quadratic lower bound for one-tape Turing machine to decide $\{ww\mid w\in\{0,1\}^*\}$
It's somewhat well-known that any one-tape Turing machine that decides $L=\{ww^R\mid w\in\{0,1\}^*\}$ requires $\Omega(|w|^2)$ time via crossing sequence arguments. But consider the language $L=\{ww\...
0
votes
0answers
11 views
What does the following notation for something in the language of a turing machine mean?
So I see the following being used in turing machines:
a configuration is $Q \times \{ y\sqcup^\omega | y \in \Gamma^\ast \} \times \Bbb N$
What is $y\sqcup^\omega$ supposed to mean and what is the ...
1
vote
1answer
47 views
Proving that there exists a Recursively Enumerable language that has a special property
In an assignment about mapping reductions, we're required to prove the following claim:
Prove that there exists $L_2\notin RE$ such that $\overline L_2 \leq_m L_2$.
We also got the following guidance: ...
1
vote
1answer
50 views
Will this function grow faster than Busy Beavers as $n \to \infty$
Consider the following function:
$$f(x)=x \uparrow ^{x} x$$
Where the notation $\uparrow$ is Knuth's up-arrow notation and $\uparrow ^{n}$ means $n$ number of up-arrows. For example, $2\uparrow ^{4}...
0
votes
1answer
64 views
Existence of infinite sets of a certain property
I've been thinking about this problem for a long time, but I can't come up with a solution. It must be proved that there exists an infinite family of infinite pairwise disjoint subsets of $\mathbb{N}$,...
0
votes
0answers
37 views
Turing degrees of subsets of Kleene $\mathcal{O}$ which are ordinal notations of subsets of the set of recursive ordinals
An ordinal $\alpha$ is said to be recursive if there is a recursive well-ordering of a subset of the natural numbers having the order type $\alpha$.
The smallest ordinal that is not recursive is ...
2
votes
1answer
32 views
Prove that $A^{(\omega)}\nleq_T A^{(n)}$
I am trying to solve Exercise 7.1.24 (i) of Computability Theory by Rebecca Weber. $A^{(n)}$ denotes the $n$-th Turing jump and $A^{(\omega)}=\{\langle x,n\rangle: x\in A^{(n)}\}$ the $\omega$-jump.
...
0
votes
1answer
24 views
Can we guarantee that the computation on the Turing machine in our case will never stop?
Assume that we have a Turing machine which on an empty input, with $n > 100$ states worked $n^{ n^n}$ steps. Can we guarantee that in this case the computation will never stop?
3
votes
2answers
52 views
Could Turing machines + random “do something” Turing machines cannot?
A machine G that outputted a bit randomly could decide any language (by guessing luckily). Formally, for all languages L, for ...
1
vote
0answers
25 views
Is there an undecidable question that doesn't ask something about Turing machines (or something Turing-complete)?
Is there an undecidable question that doesn't ask something about Turing machines (or something Turing-complete)?
The halting problem asks, given a Turing machine, ...
2
votes
0answers
100 views
Prove uncountability of R using an algorithm?
Let's say I want to prove uncountability of $\mathbb{R}$ using an algorithm (I will use Python).
I will consider reals $0 \le x \lt 1$ and represent the decimal development of $x$ with a generator.
...
0
votes
1answer
13 views
The class of primitive recursive functions
Usually the scheme of primitive recursion is defined as follows:
$$
h(x, 0)=f(x)
\\
h(x, y+1)=g(x,y,h(x,y))
$$
I was wondering whether the class of primitive recursive functions would be smaller if we ...
0
votes
0answers
37 views
Halt Turing Machines
Imagine that a friend Sheikh is capable of solving HALT. Given any instance of to the Halting problem, we can query Sheikh, if ∈ HALT, and he will instantaneously give us the right answer. He is ...
0
votes
1answer
59 views
Given FOL=Turing machines, why is SOL different than FOL?
[1] Every SOL (second order logic axiom system) has a corresponding Turing machine that verifies SOL statements, given a proof and axioms. (If this weren't the case, how could we be sure that our SOL ...
0
votes
1answer
53 views
Is FOL equivalent to Turing Machines?
Does every FOL (axiom set expressible in First Order Logic) have a corresponding Turing machine?
The proved FOL statements would be strings the Turing machine accepts.
Does every Turing machine have ...
1
vote
1answer
40 views
Infinite Time Turing Machines and the continuum hypothesis
Maybe I am misunderstanding something, but the problem described in this answer at Math.SE seems to be representable as a program for Infinite Time Turing Machines (under the assumption that any ...
0
votes
1answer
53 views
How exactly do diophantine polynomial equations map to turing machines?
From a wikipedia page:
One can write down a concrete polynomial p ∈ Z[x1, ..., x9] such that
the statement "there are integers m1, ..., m9 with p(m1, ..., m9) = 0"
can neither be proven nor ...
1
vote
0answers
21 views
A multiple choice on formal languages, Turing machines and automata
$
\newcommand{\lang}{\mathcal L}
$
I have been given the following claims about formal languages, that are either true or false:
If a language $\lang$ can be accepted with a finite automaton, it can ...
2
votes
0answers
19 views
Is a language $L$ recursive, if it and its complement $L^c$ are both recursively enumerable?
$
\newcommand{\lang}{L}
\newcommand{\Nset}{\mathbb N}
\newcommand{\Lset}{\mathcal L}
\newcommand{\Rec}{\mathcal R}
\newcommand{\RecEnum}{\Rec_\Nset}
\newcommand{\accept}{\mathbf{a}}
\newcommand{\...
2
votes
0answers
107 views
What are some theorems or hypotheses that can be tested by a two-symbol low-state Turing machine?
I'm looking for relatively interesting examples of theorems or hypotheses that could be proven (or disproven) by running at most BB(n) [S(n)] operations - on a $n-$state, two-symbol TM , where $n$ is ...
1
vote
1answer
19 views
Turing decidability
Consider intermediate chess board configuration.
L={w|w represents a board configuration, and white is guaranteed to win if it is white’s move and white plays optimally}
Is L decidable, recognizable ...
0
votes
0answers
7 views
enumerator and turning machine mapping reduction?
Let, E = enumerator M = Turing machine the language SAMEe,tm = {⟨E,M⟩ | E is an enumerator, M is a TM, and L(E) ∩ L(M) != ∅}.
Can someone give me a hint on how to prove the complement of SAMEe,tm is ...
1
vote
0answers
9 views
The problem of determining whether a given context-free grammar generates the empty string
I was unsure if you were to formulate this problem as a language would it be correct to say is ECFG = { | G is a CFG with L(G) = ∅ }? Otherwise im unsure how you would write it as a language.
0
votes
0answers
36 views
How can I read the following Turing machine?
I'm struggling to undersand the following Turing machine. When I see a,b->R, I read that as if you're at a, relace the ...
1
vote
1answer
41 views
Could the halting problem be computed in GlooP?
In Douglas Hofstadter's book Gödel, Escher, Bach, he uses 3 theoretical programming languages to describe computation.
BlooP represents primitive recursive programs.
FlooP represents general or ...
0
votes
1answer
34 views
Prove that if L is decidable then half(L) is decidable too
Let L be decidable language, and let half(L) be: half(L)={u∣uv∈L s.t.|u|=|v|}. Prove that if L is decidable then half(L) is decidable too.
I tried to build a Turing Machine to decide half(L) but none ...
0
votes
0answers
20 views
Derivation from a Turing machine
In one of my questions for my work, I have been asked to give a derivation for the word ABBA with respect to my Turing machine. I have done research into how I would do this but am unable to find ...
0
votes
0answers
25 views
Constructing multitape Turing machine L={a^k#y }
I'm having problems with construction of Turing multitape machine construction for the L= a^k#y, where y is the input data, for example abbaba and I need to check that in the y there is no a^k.
...
0
votes
0answers
22 views
Show that $L1/L2$ is semi-decidable
I am stuck at the following exercise:
Let $L_1$ be semi-decidable and $L_2$ be a decidable language over $\{0,1\}$. Show that
$$L_1/L_2 := \{w \mid \exists y \in L_2 \text{ such that } wy \in ...
1
vote
1answer
28 views
Finding an algorithm that after removing k edges we get an acyclic graph
Assuming there's an algorithm that can decide belonging to ACYCLIC in polynomial time. How can I use this algorithm in another algorithm that upon the input of a directed graph and a positive number k,...
0
votes
1answer
35 views
minimal vertex cover and P=NP
could someone please explain to me why the following occurs?
let function f be a function that finds the minimal vertex cover. meaning: f(G,v)=minimal vertex cover that v belongs to
(the graph is ...
0
votes
0answers
12 views
Proving existence of algorithm based on existence of algorithm to decide acyclic language
I am struggling to understand(actually can't understand) how to prove the following:
If there exists an algorithm that runs in polynomial time and decides belonging to ACYCLIC(the language of all ...
0
votes
1answer
39 views
proving why can't a P-Complete language exist in log-logarithmic space
I am struggling to understand why can't such a language exist(a P-Complete language in log-logarithmic space), according to the question details:
Defining a new kind of reduction: a reduction in log-...
1
vote
2answers
166 views
Constructing Turing machine for $L=\{a^n b^m, m\%n=0\}$
As it says in the title I'm struggling with a problem: construct a Turing machine that decides the language $$L= \{a^n b^m |n,m ∈ \mathbb{N} \text{ and }m\%n=0 \text{ (n divisor of m)}\} $$
It's ...
0
votes
1answer
29 views
Problem understanding Turing Halting problem
As I understand it in simple language the proof of this goes
Take a program (called oracle below) that will stop if the program it is examining never halts and never halts if the program it is ...
1
vote
1answer
38 views
Quantifying the “Complexity” or “Strength” of Axiomatic Systems
The halting Problem states that there is no Turing Maschine that is able to decide whether an arbitrary other Turing Machine will halt.
In 2016 Adam Yedidia and Scott Aaronson presented a turing ...
1
vote
1answer
31 views
partial recursive functions
Since the partial recursive functions are those that can be computed by a Turing machine, it seems that there ought to be a simple set of restrictions that can be placed on them to get the subset of ...
6
votes
1answer
33 views
Proof: Time complexity of deterministic vs nondeterministic Turing machines
I am stuck trying to understand a proof in my book for why, given a nondeterministic single-tape Turing machine $N$ that runs in time $t(n) \geq n$, the deterministic single-tape Turing machine $D$ ...
0
votes
3answers
176 views
Turing machine to the languge $\{ a^ib^j | j=2^i \}$
I need to build a deterministic turing machine to the languge:
$L = \{ a^ib^j | j=2^i \}$
I figured that I need to delete one $a$ for every ${2^i}$ $b$ until the tape contains no $a$ or $b$ or both. ...
2
votes
1answer
164 views
Question about Friedberg’s original proof of the Friedberg-Muchnik Theorem
This is Richard Friedberg’s original 1957 proof of the Friedberg-Muchnik Theorem, the origin of the ground-breaking priority argument. It is actually surprisingly understandable once you get past the ...
9
votes
1answer
150 views
What Turing degrees can truth in $\mathbb{N}$ have for different languages?
Tarski’s theorem implies that set of Gödel numbers of statements in the language of Peano arithmetic which are true in $\mathbb{N}$, the standard model of arithmetic, is not a recursive set. In fact ...
2
votes
0answers
38 views
A function that is computable but not weakly time constructible
I know that f(n) = n is a computable, weakly time constructible function but NOT a time constructible function.
But I can't think of any computable function that is not weakly time constructible. Can ...
1
vote
1answer
63 views
Are the Turing degrees of truth sets cofinal?
Godel’s Completeness Theorem, in Henkin’s version at least, says that every consistent countable set of first-order sentences has a model. Based on that, let us call a set of natural numbers a truth ...
1
vote
1answer
65 views
What is the highest ordinal that can’t be obtained from Kleene’s O with oracles?
Kleene’s $O$ is a way to use natural numbers as notations for recursive ordinals. $0$ is a notation for $0$. If $i$ is a notation for $\alpha$, then $2^i$ is a notation for $\alpha+1$. And if $\...
