Questions about Turing machines, a theoretical model of mechanical computation capable of simulating any computer program.

learn more… | top users | synonyms

0
votes
0answers
21 views

Understanding proof for Busy Beaver being uncomputable

I found this proof on http://jeremykun.com/2012/02/08/busy-beavers-and-the-quest-for-big-numbers/ and have highlighted the part I don't understand in bold. (BB(n) is defined as the number of steps ...
-2
votes
1answer
38 views

Every non deterministic Turing machine has an equivalent deterministic Turing machine Formal proof

is there exist a formal proof for Equivalence of deterministic and non deterministic Turing Machine ? i read Martin Davis and Sipser's book and there is no formal proof
1
vote
1answer
26 views

Blank tape halting problem vs. Emptiness problem ($H_0$ vs. $E_{TM}$)

I have difficulties to differentiate the $H_0$ from the $E_{TM}$ problem. What exactly means $L(M)= \emptyset $? Is it dffierent from $input~ \varepsilon$ or is $L(M)= \emptyset \leftrightarrow ...
1
vote
2answers
37 views

Non Recursively Enumerable Languages

Can someone give me an example of Non Recursively Enumerable language... i.e. A language which no Turing machine can accept ? What makes a language non recursively enumerable ?
4
votes
1answer
227 views

EQtm is not mapping reducible to its complement

This is a problem from Sipser's book (marked with an asterisk). $EQ_{TM} = \{(\langle M \rangle, \langle N \rangle)$ where $M$ and $N$ are Turing machines and $L(M) = L(N)\}$ We know that neither ...
3
votes
1answer
40 views

Is the following language recursively enumerable?

Let $L =\{ <M> | $ the amount of words $w\in\Sigma^*$ that $M$ does not halt on is finite $\}$. I would like to prove that $L\notin RE$. I can show that $\overline{L}\notin RE $ that is ...
4
votes
1answer
29 views

Reduction from ATM to ATM-complement

Is there a reduction from ATM to ATM-complement? (ATM denotes the language $\{\langle M,w \rangle \mid \text{TM $M$ accepts $w$}\}$) I have been thinking about it too much and couldn't find the ...
-2
votes
0answers
33 views

turing machine which compares 2 binary numbers

describe a turing machine having in input 2 binary numbers,it returns the second number if it is less otherwise it doesn't end. example : input 1001:1000 it returns 1000 . input 1001:10000 it doesn't ...
1
vote
1answer
22 views

With a halting oracle, can tell whether something will have finite output?

A program can have finite output, yet still not halt. Example: 1: output "Yolo" 2: output "" 3: go to step 2 This only ever outputs "Yolo", despite never ...
1
vote
2answers
39 views

Undecidable language and Turing Machines

I am reviewing some old papers for a final tomorrow, and there is a question that I'm not sure about. If a language A is Turing-Recognizable and Undecidable, what can be said of the Turing-Machine ...
6
votes
4answers
254 views

Is the halting problem always decidable for non-universal programs?

For every non-universal computable program $P$ that takes input of type $D$ does there exist some total computable function $g$ that takes an input $I$ of type $D$ and decides successfully whether $P$ ...
0
votes
1answer
42 views

Given a λ-term, can I decide which machine model I need to express it?

I am having a hard time figuring out the specific relationship, of various things in computability. So we have a hierarchy of machines, with a (real life) upper bound of Turing machines, moving on ...
1
vote
1answer
29 views

Minimal class of grammar required to run program

In computability we have the hierarchy of grammars "https://en.wikipedia.org/wiki/Chomsky_hierarchy". In this hierarchy we have many classes of grammar. This hierarchy has Turing machines at the top, ...
3
votes
2answers
342 views

Equivalence of Turing Machines

Consider the following two arguments "For every non deterministic TM M1 there exists an equivalent deterministic machine M2 recognizing the same language." "Equivalence of two Turing Machines ...
2
votes
0answers
22 views

Why we don't care about minimizing Push Down Automata & Turing Machines? [duplicate]

I never heard or read about the concepts of "Minimizing Push Down Automata or Turing Machines"? why we are not concerned about minimizing them, in general?
8
votes
1answer
140 views

Is there an algorithm for algorithms time/space complexity optimisation?

In 1950s a number of methods for circuit minimization for Boolean functions have been invented. Is there an extension of those methods or anything similar for optimising time or space complexity of ...
9
votes
2answers
338 views

How to prove that 3-coloring is decidable?

In order to prove that 3-coloring is decidable, is it sufficient to say: Each node in the graph has 3 possible colors Therefore we can enumerate over all $3^n$ possibilities and then check that no ...
8
votes
1answer
165 views

Connection between NAND gates and Turing completeness

I know that NAND gates can be used to create circuits that implement every truth table, and modern computers are built up of NAND gates. What is the theoretical link between NAND gates and Turing ...
1
vote
1answer
85 views

A question on encoding

Assuming there is a machine which can effectively calculate functions not computable by a TM (or the Church-Turing thesis as false) What can we say about aTM solving a problem encoded by this ...
4
votes
0answers
51 views

Advances in recent time in Von-neumann self replication idea

I have read about Von-neumann self replication from Theory of Self-reproducing automata, which are lecture notes reconstructed from lectures in book of the same name. Theory of Self-reproducing ...
-2
votes
1answer
57 views

Prove that {⟨M,w⟩∣M accepts w only} is unrecognizable [closed]

$$L = \{\langle M,w\rangle \mid \text{\(M\) accepts \(w\) only}\}$$ How can I prove this language is unacceptable (unrecognisable)? I think I should use a reduction, I'm not sure how.
1
vote
2answers
146 views

Turing machine - infinite tape - does that thing exist?

Can we use a Turing machine with infinite tape as a basis to prove anything disregarding the fact that such a thing can never exist? Do we have the right to regard a machine (a construct) in the same ...
4
votes
0answers
53 views

Compiler that compiles to a Turing machine?

I am interested in finding/writing a compiler that compiles a program written in a simple source language to a Turing machine (instead of assembly). Does anyone know if there is a good approach for ...
0
votes
0answers
18 views

Difficulty in the halting problem for a simple Turing machine with standard enumerations of programs and of initial tape configurations

Preparations Consider a Turing machine with just one head and one tape (on which the head may move left, move right, or remain stationary), and with just two symbols ("blank" and "non-blank"). The ...
4
votes
1answer
51 views

Difference between read-only Turing machine and non-erasing Turing machine

I cannot quite feel the difference between two models. The first one is read-only Turing machine which is basically the same as Turing machine with write protected input. See this question for ...
0
votes
0answers
35 views

What can be said about the Halting Problem if we can include the halting status to the input?

I was reading about Turing Machines and the Halting Problem, i understand that you need an oracle to decide whether given input will halt or loop forever. But why do we need an oracle if we can ...
0
votes
1answer
42 views

Turing Machine to write number

How to construct a single-tape Turing Machine which writes the number 7 in UNARY number system, leaving the tape with a delimiter symbol followed by 7 1s? So outout would be a tape contains #111111 ...
0
votes
0answers
34 views

Constructing a Turing Machine with Lambda Calculus

I'm interested in the implementation of a Turing Machine (deterministic) in Lambda Calculus. How should I proceed to do this? I am not sure on how to start since I must represent the state and ...
3
votes
1answer
40 views

The halting problem of Turing machines in view of enumeration of initial tape configurations

As far as I know, presentations of the (general) halting problem (cmp. Wikipedia) are referring explicitly to an ennumeration of (applicable) programs. For the purpose of my questions let's consider ...
-1
votes
1answer
52 views

How to make an undecidable Turing Machine decidable?

I came across the following question in my revision. I would like to know how to solve this and in general what are the techniques I can use to make an undecidable TM decidable by changing inputs? ...
-1
votes
1answer
40 views

developing a Turing Machine that checks for powers of 2

I want to write a Turing machine which checks for unary powers of 2 but without the use 0s, only accepting as input a series of 1s and dashes. I do not know of a sequence of states which would allow ...
0
votes
0answers
38 views

Help figuring out how to write the English description of a turing machine?

So I generally understand how to follow a flow-diagram of a Turing Machine, but I'm going over how to write the "steps" in English and am having a bit of trouble. The problem is as follows: "Give the ...
0
votes
1answer
41 views

k-tape turing machine

I want to create multi-tape Turing machine that recognize language {ww, $w \in {a,b}$}. With condition that max. steps is less or equal than $\frac{3}{2}\left | x \right | + 2$. Where x is word from ...
0
votes
0answers
30 views

Why is this TM only as powerful as a DFA? [duplicate]

Supposing if we restrict the Turing Machine (with single tape) to not write on portion of tape with input string why can it only recognize regular languages?
1
vote
0answers
40 views

Showing that $H'$ is not semi-decidable

I have an introductory class in computability theory and I'm currently working on my first exercises. I'm wondering if I'm on the right track with proving undecidable languages. Could you please have ...
2
votes
2answers
48 views

$A$ and $B$ are Turing-recognizable and their union is $\Sigma^*$, find a decidable $C$ with $A - B \subseteq C$ and $B - A \subseteq \overline{C}$

Sorry for long title - the question is a bit unwieldy. To state the question precisely, I'm wondering about the following proposition: Let $\Sigma = \{0,1\}$. If $A$ and $B$ are ...
4
votes
1answer
55 views

What does actually reasonable mean when we say “reasonable model of computation”?

I have seen in many text when the author says "reasonable model of computation". What does it really mean?
-1
votes
1answer
63 views

What input does this NFA accept?

I'm trying to find out what strings this NFA would accept. From what I understand, an empty string would work, as well as any string that has nothing but 0's. But for strings containing 1's, I'm a ...
2
votes
1answer
228 views

Is Turing machine a programmable machine or Is it like a fixed program computer?

We all know Random Access Machine (RAM) models are programmable machines. We can program a same machine for different problems with the help available instruction set. But in the case of Turing ...
0
votes
3answers
85 views

Can a Turing Machine have infinite accept states?

I'm still fairly new to Turing Machines, but I've been doing some research. I know that a Turing Machine can have an infinite tape and that it requires a finite number of states, but does it ...
1
vote
0answers
50 views

Defining a Turing machine for $0^n 1^n 0^1$ [closed]

I am new to understanding Turing machines and I am trying to define a Turing machine that for the language $L = 0^{n}1^{n}0^{n}$. I am not quite sure how to give an implementation level description ...
2
votes
1answer
58 views

Can we use a different encoding scheme to solve an unsolvable language?

Say we have a particular decision problem and that we have an alphabet and an encoding scheme, which gives us a language L that we say is not recursive (i.e. we do not have a Turing Machine that can ...
3
votes
1answer
42 views

Set of Turing machines $S$ such that any $A \in S$ halts on input the description of any $B \in S$

Does there exist a maximal set of Turing machines $S$ over the alphabet $\{0,1\}$ such that any $A \in S$ halts on input the description of any $B \in S$? Take S to be the set of deciders. Then S ...
1
vote
1answer
62 views

Proving that $A=\{w_{2i}|w_{2i}\not\in L(M_i)\}$ is not Turing-recognizable

In this problem, $w_{2i}$ is the $2i$th string in the lexicographic order of binary strings and $M_i$ is the TM whose binary code is $w_i$. We are given the diagonalization language $A_D=\{w_i \mid ...
-2
votes
1answer
59 views

Turing machine for adding numbers

I'm having trouble in a certain problem. I have to write a TM that gets as an input strings $\#x\#y$ such that $x,y \in \{0,1\}^*$, and writes to the tape the output $z\#x\#y$ where $z = x+y$, all ...
4
votes
2answers
150 views

What is an “encoding” of a TM?

I'm currently working on a reduction from $A_{TM}$ to another language, and have been reading through some example proofs. I've come across the situation where, for example, we have $L = \{ \langle ...
7
votes
1answer
113 views

Understanding of Turing's Answer to the Entscheidungsproblem

I apologize if this question has been asked before, but I was not able to find a duplicate. I have just finished reading The Annotated Turing and I am a bit confused. From what I understand, the ...
2
votes
0answers
38 views

Expressing classic automata in modern terms

This semester I was introduced to finite automata (FSM), then pushdown automata (PDA), and now the Turing machine (TM). Granted that there're many possible implementations of these abstractions ...
0
votes
1answer
82 views

Are “TM M accepts some string of length greater than 100” and “TM M accepts some string of length at most 100” decidable?

I have two questions as in the title: TM M accepts some string of length greater than 100 TM M accepts some string of length at most 100 Since 1. is infinite, we can rephrase question as "does TM ...