Questions tagged [turing-machines]

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

Filter by
Sorted by
Tagged with
2
votes
1answer
43 views

Timely lower bounded Turing machines

Let M be a deterministic Turing machine wich has the properties: 1) $\forall x,y \in \Sigma^* : t_M(xy) \ge t_M(x) + t_M(y)$ 2) $\forall a \in \Sigma: t_M(a) \ge 1$ (Also 2) should be obvious for ...
1
vote
1answer
208 views

Prove that $H$ reduces to $H\varepsilon$

I have to prove that $H_\varepsilon = \{<M> \mid M\ \text{halts on input }\varepsilon\}$ reduces to $H$ (the halting problem). I am very confused how to PROVE it, I mean it is clear that we can ...
1
vote
1answer
864 views

A second question on “Show a TM-recognizable language of TMs can be expressed by TM-description language of equivalent TMs” [duplicate]

Let B={M1,M2,...} be a Turing-recognizable language consisting of TM descriptions. Show that there is a decidable language C consisting of TM descriptions s.t. every machine in B has an equivalent ...
1
vote
1answer
378 views

Turing machine to compute $⌈\log_2n⌉$ with 1 tape and unary input/output

I'm trying to figure out how to make the action table for a Turing Machine computing $⌈\log_{2}(n)⌉$. The input and output shall be unary (meaning $3$ should represent $111$). I can only deal with 1 ...
1
vote
2answers
317 views

Question for “Only if” part for the theorem “A language is Turing-recognizable iff some enumerator enumerates it.”

I am trying to prove the theorem A language is Turing-recognizable iff some enumerator enumerates it. I proved the "if" part, but I have no idea of proving the "only if" part, so I searched a ...
1
vote
2answers
13k views

Turing machine that increments a binary number by 1

I was asked to construct a Turning Machine that computes the increment of a binary string by 1- The Turing Machine receives a binary string and accept a string which is an increment by 1 of the input, ...
1
vote
2answers
1k views

P=NP, isn't it?

Cook and Levin showed in 1971 how deterministically in polynomial time from every non deterministic Turing machine M, that halts in polynomial number of moves/steps, and string w to create the boolean ...
0
votes
1answer
230 views

How can a Turing machine write the description of the n-th Turing machine?

I am trying to interpret the following problem: "Describe an algorithm for a Turing machine which receives the integer n as input and proceeds to write the description of the n-th Turing machine from ...
0
votes
1answer
1k views

Turing machine deciding $\{1^{2^n} : n \geq 0 \}$ [duplicate]

How can I design a Turing machine that accepts the language $\{1^{2^n} : n \geq 0\}$? Here is my attempt: [![enter image description here][1]][1]
35
votes
5answers
14k views

What does being Turing complete mean?

I see that most definitions of what it is to be Turing-complete are tautological to a degree. For example if you Google "what does being Turing complete mean", you get: A computer is Turing ...
6
votes
1answer
10k views

Undecidable among these for turing machine

Below are two questions I found in Theory of Computation book but couldn't find its correct answers, can anyone please give correct answers with explanation? It is undecidable, whether an arbitrary ...
15
votes
5answers
4k views

Turing machine + time dilation = solve the halting problem?

There are relativistic spacetimes (e.g. M-H spacetimes; see Hogarth 1994) where a worldline of infinite duration can be contained in the past of a finite observer. This means that a normal observer ...
9
votes
1answer
15k views

How do you classify properties as Trivial and Non-trivial? [duplicate]

I understand what Rice's theorem states and what Trivial and Non-trivial properties mean. However, when given some property, I am having a hard time seeing if it is Trivial or Non-trivial. Can someone ...
12
votes
1answer
6k views

What is the difference between RAM and TM?

In algorithm analysis, we assume a generic one processor Random Access Machine (RAM). As far as I know, the RAM machine is no more efficient than the Turing machine. All algorithms can be implemented ...
12
votes
1answer
3k views

What is the relationship between Turing Machines with a finite tape and Finite State Automata?

I seem to recall from an undergraduate class that for a Turing Machine with a finite tape there will always exist a corresponding Finite State Automata, but I've been unable to find this confirmed ...
14
votes
2answers
8k views

Is it decidable whether a TM reaches some position on the tape?

I have these questions from an old exam I'm trying to solve. For each problem, the input is an encoding of some Turing machine $M$. For an integer $c>1$, and the following three problems: ...
11
votes
2answers
4k views

Clear, complete, proof that a language is Turing Compete?

I have seen web sites that purport to "prove" that HTML5+CSS is Turing Complete. I have seen web sites that purport to "prove" that SQL is Turing Complete. I have seen a bunch of web sites that ...
6
votes
4answers
3k views

Can we write algorithms without conditional statements?

Regarding turing completeness, i read that for a language/machine to be turing complete it is required that it has some sort of conditional. Consider the factorial problem, we would typically define ...
29
votes
1answer
8k views

Quantum Computing and Turing Machines: Are Turing Machines still an Accurate Measure?

In class last week, my professor commented and said that Turing machines are used as a standard measure/model of what is computable and are a helpful basis of discussion for that subject. She also ...
8
votes
3answers
8k views

What is the difference between a TM accepting and deciding a language?

Frankly I'm very uncomfortable with the material right now. There are some things I can understand, but many I still do not. My first assignment is asking me in one question (which I do know how to ...
8
votes
6answers
6k views

The first Turing machine

Does anyone know how efficient was the first Turing machine that Alan Turing made? I mean how many moves did it do per second or so... I'm just curious. Also couldn't find any info about it on the web....
4
votes
1answer
6k views

Can you recognize or decide if a Turing Machine has an infinite sized language?

That is, can you build a Turing Machine that, if given a Turing Machine as input, can decide (or at least recognize) if the inputted Turing Machine has an infinite number of strings in its language? ...
4
votes
1answer
2k views

Why is simulation by non deterministic Turing machine faster than a deterministic one?

A deterministic universal Turing machine $U_D$ can simulate a deterministic turing machine $M_D$ in $O(T(n)log(T(n)))$ where $M_D$ runs in $O(T(n))$. But I came across an exercise in Sanjeev Arora and ...
16
votes
1answer
1k views

Is the unsolvability of the N-Body Problem equivalent to the Halting Problem

There is no general analytic solution to the n-body problem that can produce an analytic function which can be used to give an n-body system's state at arbitrary time t with exact precision. However, ...
10
votes
6answers
567 views

Undecidable problems limit physical theories

Does the existence of undecidable problems immediately imply the non-predictability of physical systems? Let us consider the halting problem, first we construct a physical UTM, say using the usual ...
9
votes
2answers
196 views

Is the leapfrog automata problem in P?

My question is whether a specific decision problem—finding a computation path through a "leapfrog automaton"—is in P or not. It's straightforwardly in NP, and it resembles the hamiltonian ...
14
votes
3answers
2k views

undecidable problem and its negation is undecidable

A lot of "famous" undecidable problems are nonetheless at least semidecidable, with their complement being undecidable. One example above all can be the halting problem and its complement. However, ...
7
votes
3answers
1k views

Please explain this formal definition of computation

I am trying to attack TAOCP once again, given the sheer literal heaviness of the volumes I have trouble committing to it seriously. In TAOCP 1 Knuth writes, page 8, basic concepts:: Let $A$ be a ...
6
votes
3answers
701 views

Is there a single valid definition for a Turing Machine, or is it mutable?

I'm just learning about Turing Machines, and I'm a bit confused by the difference in formal description between Wikipedia and my textbook. My textbook says the following: $$M=\langle Q,\Sigma,\Gamma,...
6
votes
4answers
650 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$ ...
6
votes
1answer
1k views

Where am I wrong?: “countability” and “recursive enumerability”

I have a a few fundamental doubts in recursive enumerability and countability and below, I have written what I understand them to be with proofs. But there are contradictions at the end. What is wrong ...
3
votes
5answers
2k views

What would show a human mind is/is not reducible to a Turing machine?

In computer science it is often assumed that a human mind can be reduced to a Turing machine. This is the assumption that underlies the field of artificial intelligence. However, it is an assumption,...
2
votes
2answers
5k views

Is the language of TMs that halt on some string recognizable?

I would like to show that the following language is recognizable: $$L:= \{ \langle M \rangle \mid M \text{ is a TM that halts on some string}\}.$$ How do I go about showing that this language is ...
2
votes
1answer
2k views

Is a partial function Turing-computable?

From my understanding for a function to be considered Turing-computable the Turing machine which computes it must terminate for all inputs (according to this http://planetmath.org/turingcomputable and ...
12
votes
2answers
3k views

Are all context-sensitive languages decidable?

I was going through the Wikipedia definition of context-sensitive language and I found this: Each category of languages is a proper subset of the category directly above it. Any automaton and any ...
10
votes
4answers
4k views

The bounded halting problem is decidable. Why doesn't this conflict with Rice's theorem?

One statement of Rice's theorem is given on page 35 of "Computational Complexity: a Modern Approach" (Arora-Barak): A partial function from $\{0,1\}^*$ to $\{0,1\}^*$ is a function that is not ...
9
votes
4answers
3k views

Can a Turing Machine (TM) decide whether the halting problem applies to all TMs?

On this site there are many variants on the question whether TMs can decide the halting problem, whether for all other TMs or certain subsets. This question is somewhat different. It asks whether ...
7
votes
2answers
868 views

Machines in P undecidable?

Given a Turing machine $M$, we say that $L(M) \in P$ if the language decided by the machine can be decided by some machine in polynomial time. We say that $M \in P$ if the machine runs in polynomial ...
6
votes
1answer
710 views

Is a secondary TM sufficient to detect all loops?

Procedure: Start a secondary TM in parallel with the first, but have the second perform exactly 1 step each 2 steps the first TM performs (i.e. it runs at half speed). If the second machine ever ...
5
votes
2answers
9k 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 ?
5
votes
3answers
14k views

Decidable languages kleene star closure - question on a proof

I read a proof on the closure of decidable languages under kleene star. It begins by saying that the turing machine we want to find would non-determistically split the input string and then use the ...
5
votes
2answers
754 views

Why is the language of TMs that have some quadratic time bound undecidable?

The language in question is $L = \{M : M \text{ is a Turing machine that halts in } 100n^2 + 200 \text{ time}\}$. Attempt 1 Suppose $L$ is decidable. Let $M_1, M_2, \ldots$ be the Turing machines in ...
5
votes
2answers
2k views

Does every turing machine have an equivalent, single-state, n-tape turing machine?

Is it the case that every problem computable by a Turing Machine can also be represented by some kind of equivalent n-tape Turing Machine which one has only one state? (We can assume that the accept ...
4
votes
4answers
1k views

What approaches are most useful when proving uncomputability of a given function?

I'd like to understand what approaches should one adopt when deciding/proving that a given function F is uncomputable, by any Turing Machine (TM). The ones I've tried so far are as follows: Reduction,...
3
votes
2answers
2k views

Is it possible to ever define $L(M)$ of a given Turing Machine, $M$?

In class, we were discussing creating a Turing Machine $M$ based on the set of input strings it should accept, i.e. define a Turing Machine that accepts only the input $\{ w\ \#\ w\ |\ w \in \{0,1\}^*\...
3
votes
2answers
4k views

Proving the set of finite languages is countable without using the union of countable sets

The list of finite languages over a finite alphabet is countable. I could prove it by saying that the list of languages of size 1 is countable, the language of size 2 is countable, and so on. Then I ...
1
vote
3answers
2k views

How to replace one symbol with two on Turing machine's tape

I want to implement following algorithm on Turing machine: rewrite binary numbers to their unary counterparts. For example: 101 will be rewritten to a string of 5 consecutive bars (wikipedia) ...
1
vote
1answer
1k views

which of the following languages are Recursively Enumerable?

Which of the following languages are recursively enumerable? A={⟨M⟩∣ TM M accepts at most 2 distinct inputs} B={⟨M⟩∣ TM M accepts more than 2 distinct inputs} For first language I think that we can ...
1
vote
2answers
512 views

Can we convert any given turing machine to a turing machine with only 2 states? if so, how?

So i remember reading somewhere that we can convert any turing machine into a turing machine with 2 states (or 3, i don't remember) but there was no proof for it and i couldn't find it either So my ...
-1
votes
1answer
317 views

Is the infinite program Turing-recognizable/decidable?

Imagine we have a program which does an infinite loop: while(true){loop} We run the program on a linux machine(assume the compilation is ok), then this linux ...