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
13
votes
3answers
18k views

Why is this true: “There are countably many Turing Machines” [duplicate]

It is said that there are uncountably many languages but only countably many Turing Machines. Could someone make this clear to me? And this doesn't mean that the set of TM is finite, yes?
8
votes
1answer
12k 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 ...
10
votes
1answer
4k 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 ...
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 ...
26
votes
1answer
7k 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 ...
14
votes
2answers
7k 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: ...
10
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 ...
7
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....
7
votes
2answers
158 views

Computability of equality to zero for a simple language

Suppose we have a tree in which leaves are labeled with a set of numbers $L$, and internal nodes with a set of operations $O$. In particular $L$ can be $\mathbb{N}, \mathbb{Z}$ or $\mathbb{Q}$, and ...
4
votes
1answer
1k 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 ...
4
votes
1answer
5k 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? ...
11
votes
6answers
527 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
154 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 ...
7
votes
3answers
7k 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 ...
13
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
4answers
567 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
3answers
623 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
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
1k 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
4k 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
2k 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 ...
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 ...
9
votes
4answers
3k 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 ...
6
votes
3answers
2k views

Is there an algorithm for converting Turing machines into equivalent Lambda expressions?

We know that Turing machines and Lambda Calculus are equivalent in power. And There are proofs for that, I'm sure. But is there an algorithm, a systematic way for us to convert a Turing machine into ...
6
votes
1answer
587 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
3answers
13k 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
8k 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 M,...
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,...
4
votes
2answers
557 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 ...
3
votes
2answers
1k 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
3k 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
334 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
151 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 ...
8
votes
0answers
908 views

Complexity of Sorting Integers on a Multitape Turing Machine

How expensive is sorting integers on a Multitape Turing Machine? Well known sorting algorithms, like quicksort, tend to rely on jumping / indirect-access being cheap. But MTMs have no indirect access.....
8
votes
1answer
681 views

Prove n! is fully time constructible

We just finished our "Time constructability" lesson in class last week, and we, for example's sake, showed that $n^k, 2^n$ are fully time constructible, i.e. there exists a (multi-tape deterministic) ...
8
votes
1answer
1k views

Combinational Logic Circuits and Theory of Computation

I'm trying to link Combinational Logic Circuits ( computers based on logical gates only ) with everything I have learned recently in Theory of Computation. I was wondering whether combinational ...
8
votes
2answers
622 views

How can a cyclic tag system halt with an output?

For example, we can say we have a abstract program that, given a finite binary string as input, removes all of the zeros (i.e. 0010001101011 evaluates to 111111), which is definitely a Turing-...
7
votes
0answers
1k 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 ...
6
votes
2answers
454 views

Universal binary rewriting system

What is the simplest example of a rewriting system from binary strings to binary strings $$f:\Sigma^*\rightarrow\Sigma^*\qquad\Sigma=\{0,1\}$$ that can perform universal computation? Binary string ...
5
votes
1answer
381 views

For the time hierarchy theorem, how is the input translated efficiently?

I'm trying to understand the proof of the time hierarchy theorem appearing in sipser's book. The proof requires a TM M to simulate an arbitrary TM N without too much slowdown. In particular, it is ...
5
votes
2answers
188 views

Proof of Space Hierarchy Theorem incompatible with Linear Speed Up Theorem for time

In this proof of the Space Hierarchy Theorem the following language is defined $$ L = \{ (\langle M \rangle, 10^k) : M \mbox{ does not accept } (\langle M \rangle, 10^k) \mbox{ using space } \le f(|\...
5
votes
2answers
2k views

Union of R.E. and Non R.E. language

Let \begin{align*} L_1 &=\{\langle M,w\rangle \mid M\text{ halts on }w\}\\ L_2 &=\{\langle M,w\rangle \mid M\text{ does not halt on }w\}\,. \end{align*} Here $M$ represents encoding ...
5
votes
0answers
2k views

Prove that turing machines and the lambda calculus are equivalent

It is known that a turing machine and the lambda calculus are equivalent in power. I now want to try to prove this myself. I think proving that the lambda calculus is at least as powerful as a turing ...
4
votes
2answers
592 views

Can the Lambda Calculus or Turing Machines model signals, callbacks, sleep/wait, or buses?

I have a deep appreciation for formalisms like the Turing Machine and the $\lambda$-Calculus, and enjoy studying them and learning more about how they relate to physical computers. I am now learning ...
4
votes
1answer
331 views

Is a Turing Machine that only takes strings of the form $0^*$ Turing Complete?

You have a Turing machine that only processes input on the form $0^*$. If it is given an input without 0's, it will simply halt without accepting or do anything else. Is it Turing Complete? The set $...
4
votes
1answer
4k views

Proving ALLTM complement not recognizable

A few definitions.. $$ \begin{align*} \mathrm{ALL}_{\mathrm{TM}} &= \Bigl\{\langle M \rangle \,\Big|\, \text{$M$ a Turing Machine over $\{0,1\}^{*}$},\;\; L(M) = \{0,1\}^{*} \Bigr\} \\[2ex] \...