# 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
Filter by
Sorted by
Tagged with
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 ...
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 ...
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 ...
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 ...
59 views

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 ...
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: ...
50 views

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 ...
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 ...
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 ...
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.
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 ...
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 ...
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 ...
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 ...
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. ...
22 views

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 ...
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 ...
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 ...
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$ ...
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. ...
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 ...
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 ...
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 ...
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 \$\...