Skip to main content

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
-2 votes
0 answers
16 views

In the Binary Domino problem, the size of the alphabet is 2 (i.e. each label on the sides of the dominos is either a or b). Is the BDOM decidable? [closed]

In the Binary Domino problem, BDOM, the size of the alphabet is 2 (i.e. each label on the sides of the square dominos is a single letter, either a or b). Is the BDOM decidable?
Matthew Benjamin's user avatar
3 votes
2 answers
320 views

Turingmachine for decision of mathematical conjecture

A consequence of the Halting-Problem is that there isn't a Turingmachine for the Entscheidungsproblem of Hilbert. An exersice I have to work on has the question: Does there exist a TM that prints 1 if ...
SooS's user avatar
  • 31
3 votes
2 answers
216 views

Proving a corollary of Trakhtenbrot theorem

In Sets, Logic, Computation, Trakhtenbrot's theorem is stated as follows: Theorem 15.21 (Trakhtenbrot's Theorem). It is undecidable if an arbitrary sentence of first-order logic has a finite model (i....
John Davies's user avatar
0 votes
0 answers
67 views

Turing recognizable, unrecognizable languages

What are examples of a a) language L such that both L and comp(L) are both unrecognizable b) decidable language D, and an unrecognizable language N, such that their union D ∪ N is decidable c) ...
Miras Shaltayev's user avatar
0 votes
0 answers
17 views

Let L = {1^s| such that there exist s consecutive 1s in the (decimal) expansion of π}. Is the language L Turing-decidable?

Let $L = \{1^s|$ such that there exist $s$ consecutive 1s in the (decimal) expansion of $\pi\}$. Is the language $L$ Turing-decidable? At first glance it seems like it would not be Turing-decidable ...
Noah Hendrickson's user avatar
1 vote
2 answers
55 views

Understanding the proof of the uncomputability of the "productivity function"

I'm not following this proof of what Bools,Burgess,Jeffrey call the productivity function. The proof states that the value from the productivity function is not computable. They call it $s$, and it ...
Burnsba's user avatar
  • 1,025
0 votes
0 answers
11 views

Is there some shared structure between Chaitin's constants of similar systems?

Since it is possible to approximate Chaitin's constant ($\Omega$) for some systems, is it known whether these numbers are somehow related to another when considering similarly operating Turing ...
2080's user avatar
  • 150
2 votes
0 answers
89 views

If A is decidable, is A* decidable?

my thought process is that since you can construct a Turing machine that decides the language, all you would need to do is construct it so that it continues to accept every time the same valid strings ...
papayaaa's user avatar
0 votes
0 answers
51 views

Deterministic Turing Machine for $L=\{ww : w\in \{0,1\}^{*}\}$ with restrictions.

I want to design a deterministc TM for the $L$ in the title, I've seen before for $$A=\{0,1,X,Y\} \hspace{0.5cm} B=\{0,1,\$\}$$ $A$ is for the input alphabet and $B$ is for the tape alphabet. (...
Katalanhyani's user avatar
0 votes
0 answers
44 views

Number of Turing machines with $n$ states and an alphabet of size $c$ characters.

I want to count how many Turing machines there are with $n$ states (ignoring the rejecting and accepting states) and with an alphabet (input and working) of size $c$ characters. I have a solution, but ...
Andrew's user avatar
  • 1
2 votes
0 answers
55 views

Universal Turing Machines with Simple Encodings of Their Tape.

I am seeking a small $2$-symbol Universal Turing machine $U$ such that if $T$ is a Turing machine written to the tape of $U$ somehow, and I wish for $U$ to simulate $T$ with its tape initialized to $n$...
Matthew Bolan's user avatar
0 votes
0 answers
56 views

Arithmetization of Turing machines

Refer to Turing's 1936 paper, page 248, last paragraph. I present the paragraph in verbatim below : The expression "there is a general process for determining..." has been used throughout ...
Ajax's user avatar
  • 345
1 vote
1 answer
98 views

Why is a set is decidable iff it is the domain of a computable function

I'm studying three paradigms of computability theory: Godel's, Turing's, and von Neumann's. In the first two, it is given as a theorem that $f$ is a computable function iff its domain $S$ is decidable ...
lafinur's user avatar
  • 3,344
1 vote
1 answer
29 views

Proving that a Turing machine is deterministic using instantaneous descriptions

We define an instantaneous description of a Turing machine as a word $\alpha p \beta$, with $\alpha, \beta \in \Sigma^{*}$ and $q \in Q$, s.t. if $$ d = \alpha_1 \ldots \alpha_n q \beta_1 \ldots \...
lafinur's user avatar
  • 3,344
1 vote
2 answers
141 views

Curry’s paradox in Turing machine land?

Background There’s an excellent question on MathOverflow that talks about the following: imagine that $M$ is a TM that searches over all ZFC proofs and halts if and only if it finds a proof that it ...
templatetypedef's user avatar
0 votes
2 answers
65 views

Why is this undecidability proof for $E_{TM}$ valid?

I understand what it means to reduce a problem and how this is used to show by contradiction that the theorem is true. Question What troubles me is the way the proof is formulated. In step 1.2 it is ...
Noah S.'s user avatar
1 vote
2 answers
129 views

If we had an algorithm for entscheidungsproblem, how do we exactly construct an algorithm for the halting problem?

The resources I found pretty much all end with this "obvious" statement, which I can't figure out how. In plain language how to do this exactly? Edit: sources I have found: https://simple....
Alex's user avatar
  • 336
2 votes
1 answer
153 views

Are these definitions of oblivious Turing machines equivalent?

I'm confused about the definition of an oblivious Turing machine. According to this answer (and the comments below it), it can be defined as follows. A type-1 oblivious Turing machine is a new kind ...
WillG's user avatar
  • 6,607
0 votes
0 answers
29 views

PREFIX-FREE = {$\langle G\rangle$ | G is a CFG where L(G) is prefix-free} is undecidable by reduction to A_{TM}?

Let PREFIX-FREE = {$\langle G\rangle$ | G is a CFG where L(G) is prefix-free}. Prove PREFIX-FREE is undecidable. I've seen several solutions to PREFIX-FREE by reduction to PCP (here). In my course we'...
guglielmo's user avatar
0 votes
0 answers
47 views

$2023_{TM} $ = {$⟨M⟩$| M is a TM and there exists an input w on which M moves the tape head to the left of cell number $2023$} is decidable

Consider the following problem: Given a semi-infinite tape Turing Machine M, determine if there exists an input w on which M moves the tape head to the left starting from cell number 2023 (i.e., if at ...
guglielmo's user avatar
0 votes
1 answer
43 views

Is this language context-sensitive?

I want to make a grammar for the language consisting of all strings of $a, b$ and $c$ (including $\epsilon$) such that the number of $a$'s, $b$'s and $c$'s is equal. The idea is to use nonterminals $A,...
likeAvirgin's user avatar
1 vote
1 answer
76 views

What are provers and verifiers in computation theory?

Recently I was studying a computation and complexity theory on my own and I have a problem of grasping formally a concept of a prover and a verifier. I think I understand it on the intuitive level, ...
MI00's user avatar
  • 277
0 votes
0 answers
36 views

Variant of a Turing machine

Given a standard Turing Machine with the transition function: δ(q,a)=(p,b,L/R), meaning the machines head reads 'a' then writes 'b' instead of 'a' then moves to state 'p' Given a variant to the ...
mpdxd01's user avatar
0 votes
0 answers
57 views

Is this a valid Busy Beaver lower bound and does it help?

I was struck by a comment someone made about the recent BB(748) ZFC-independence result being shortened to BB(745) pointing out that while this reduced the number of TM states by only 3 it reduced the ...
Ymareth's user avatar
  • 101
0 votes
0 answers
42 views

Clocked Turing Machine in Undecidability proofs

If we are dealing with the following reduction: $$\overline{K} \leq \{ p ∣ \forall y: M_p(y) \downarrow \} $$ one of the possible definitions for $M_p[x](y)$ is the following: ...
houda el fezzak's user avatar
0 votes
1 answer
106 views

Help understanding the proof that $L = \{ \langle M \rangle \mid M \text{ is a TM that accepts the input string } 101\}$ is undecidable

I understand of the existence of Rice's Theorem, however, I want to understand better how this reduction is formed. My professor gives the answer as follows: "By contradiction, assume that $L$ is ...
codeing_monkey's user avatar
9 votes
0 answers
152 views

Second place in the Turing Machine race

Given a deterministic Turing machine T which begins on an infinite blank strip, let its growth rate $G_T(t)$ represent the number of non-blank squares after the machine is run for $t$ time steps. It ...
volcanrb's user avatar
  • 2,796
2 votes
1 answer
295 views

Multi-head Turing machine can be simulated by a single-tape deterministic Turing machine

A multi-head Turing machine is a Turing machine with a single tape but multiple heads. Initially, all the heads are positioned above the first cell of the input. The transition function is modified to ...
guglielmo's user avatar
1 vote
1 answer
127 views

Why is reduction from Hamiltonian cycle to Hamiltonian path wrong?

Wiki link states that you are able to reduce from HC to HP by vertex cleaving. In the other direction, the Hamiltonian cycle problem for a graph G is equivalent to the Hamiltonian path problem in the ...
Peter HU's user avatar
  • 141
0 votes
0 answers
49 views

Showing that the language of this constrained form of the PCP is decidable

Problem: Prove that the language $L = \\{\langle P \rangle \mid P \text{ is an instance of PCP with a match in which the } i\text{th domino is used at most } i \text{ times}\\}$ is decidable. ...
codeing_monkey's user avatar
2 votes
1 answer
139 views

No Turing machine can detect whether another Turing machine will halt in all cases. But exactly how well can one do?

The undecidability of the halting problem implies that no Turing machine can determine whether an arbitrary Turing machine passed to it will halt or not on a given input. However, we can devise ...
M. Sperling's user avatar
0 votes
1 answer
59 views

Is the halting set a subset of the natural numbers?

I'm very new to this area of math, so forgive me if this question doesn't make sense. I am searching for a set X ⊆ N (the naturals) that follows certain decidability rules, and am attempting to work ...
figbar's user avatar
  • 157
1 vote
1 answer
63 views

Union of complement of P and Q is in coNP

Given two problems $P$ and $Q$ are in NP and coNP respectively. Defined whether Union of complement of P and Q is in coNP. (It is true and I have proved this) Union of complement of P and Q is in NP. ...
ohana's user avatar
  • 869
0 votes
1 answer
70 views

Problems with universal encoding format for Turing Machines?

When one talks about decidable and semi-decidable languages, it is inevitable that the concept of "encoding a Turing machine as a (binary) string" will come up. And at first glance this ...
adam dhalla's user avatar
1 vote
0 answers
121 views

is the normal proof of halting problem undecidability is wrong?

The normal proof goes as follows: if H(f) is a program that takes the source code of any program f and return whether it halts, we define G to be if(H(G)){ loop forever } else { halt } Which is a ...
Strawberry Animations's user avatar
7 votes
0 answers
141 views

Length of the longest non-infinite path given by a pattern of length n.

Before I get into it, my question is what's the next step in finding the longest path for a pattern length $n$? Imagine if you will, an integer grid. You start a bot off at $(0,0)$ with a pattern, [...
Jacob Claassen's user avatar
0 votes
0 answers
42 views

Equivalence in adaptive vs non-adaptive queries in complexity

I am working on the following problem from Complexity by Ashcroft: We say that an algorithm $A$ makes non-adaptive queries to an oracle if it selects all of the strings on which it will query the ...
user avatar
3 votes
1 answer
61 views

A bounded sequence with no computable convergent subsequence

Given a sequence of reals $(a_n)_{n=0}^\infty$, we can define a subsequence of it to be computable if the set of its indexes is a computable set. using this definition it's not too hard to see that ...
Ynir Paz's user avatar
  • 607
0 votes
0 answers
220 views

Proving inverse of a computable function is computable

Let $f:\omega\to\omega$ be a bijective computable function. I am trying to prove that $f^{-1}$ is computable. I tried searching online this result, but I couldn't find any result that convinced me ...
mathlearner98's user avatar
1 vote
0 answers
160 views

Turing Machine exercise

I would like to design a Turing machine that takes as input a tape with a sequence of As and counts them, writing the result in decimal at the end of computation. Example: initial tape: $AAAAAAAAAAA \...
banana23's user avatar
1 vote
0 answers
63 views

Decidable formal language with a finite but non-computable size

I'm looking for a formal language that has the following properties: Contains finitely many words (and you can prove it). Decidable/recursive (there's a Turing machine that always halts, that can ...
koorkevani's user avatar
1 vote
2 answers
108 views

Is someone trying to solve problems by building all possible proofs using all possible rules of inference? [closed]

We obviously can construct a program that, starting with ZFC (or any other theory) axioms, would use all possible rules of inference to get all possible proofs constructible in ZFC. (There would be ...
ThePhilosopher's user avatar
1 vote
0 answers
50 views

Infinite Recursion as the Intuitive Foundation for the Halting Undecidability Proof

all, I was wondering if my intuitive understanding of why the halting problem is undecidable is actually correct? TLDR: Halting problem is undecidable because it leads to infinite recursion and never ...
boinka's user avatar
  • 145
1 vote
0 answers
63 views

What exactly does "a sufficiently expressive procedure for enumerating theorems" mean in the context of the incompleteness theorems?

Whenever I Google to try to find an actual formal statement of the first incompleteness theorem (as opposed to all the oversimplified explanations that talk about "true but unprovable theorems&...
Mikayla Eckel Cifrese's user avatar
0 votes
0 answers
37 views

Is there any standard notation for turing machines outcomes?

On 2 symbols 1-state turning machine, there are 64 posible machines taking into account their transition tables. One of this machines could be: $$A0:0LA$$ $$A1:0RH$$ (meaning: in state A, reading a 0, ...
Eduard's user avatar
  • 304
0 votes
0 answers
62 views

Understanding Halting Problem, regarding the "input"

Before asking: My background is natural science and a bit of "coding" skills. I didn't study rigorous mathematics and logics since undergrad freshman, and this question is based on some ...
Hojin Cho's user avatar
  • 164
0 votes
0 answers
215 views

Minimum Number of states for a Turing Machine

I am looking for a Turing Machine $M$ with $k$ states such that there is no other Turing Machine $M$' with fewer than $k$ states that recognizes the same language as $M$ (i.e., $L(M) = L(M')$). We ...
Srcoute's user avatar
0 votes
0 answers
24 views

Is the average number of steps of a $n$-state $k$-symbol Turing uncomputable?

There are finitely many $n$-state and $k$-symbol Turing machines. Call the number $N(n,k)= (2k(n + 1))^{kn}$ (according to Wikipedia https://en.wikipedia.org/wiki/Busy_beaver). Each of them either ...
Frederik Ravn Klausen's user avatar
1 vote
0 answers
95 views

Prove that NP ∩ co-NP closed under concatenation

I'm preparing for a test, and I've stumbled across the next question: "Prove that the complexity class NP ∩ co-NP is closed under concatenation." So my idea was that I know that a language $...
Zig302's user avatar
  • 11
5 votes
2 answers
182 views

Axiomatization of reducibility notions

In computability theory, there are many notions of reducibility (such as Turing reducibility, enumeration reducibility, many-one reducibility, etc.). I am curious—has there been any attempt to ...
Gavin Dooley's user avatar
  • 1,055

1
2 3 4 5
20