New answers tagged

1

I assume that a Turing machine will nor be able to reason that the liar paradox statement is a logical paradox with no decidable answer and will be stuck forever. Why do you assume that? It's perfectly possible for a Turing machine to recognize a specific paradox and to have logic systems that include the concept of paradox. Also, note that undecidability ...


1

I'm not sure I completely understand what you mean. But it looks like just a common misconception. When we say X is undecidable, it means it isn't possible to find an algorithm that could always generate the correct output for every valid input. But it's possible for an algorithm to generate the correct output only for some inputs, while giving a third ...


1

The question is unclear with respect to how exactly it is supposed to be formalized. But formalized must it be because it is asking about the ability of Turing machines to perform certain tasks. So I am going to go ahead and formalize is as best as I can. Let ZFC be the first-order theory of Zermelo-Fraenkel set theory. We are going to use it as the meta-...


1

Humans have found undecidability theorems. There is no reason known why an artificial intelligence cannot be built that matches what humans can do intelligence wise (although what is currently fashionable seems to be just pattern matching on a massive scale, which is not going to get you very far), therefore there is no reason known why an artificial ...


1

We will show that $A_{TM}$ is complete for your class. In order to show that, we need to show that for every language $A\in L\cup \{A_{TM}\}$, it holds that $A\le_L A_{TM}$. First, if $A=A_{TM}$, then the trivial reduction suffices. That is, a reduction that given input $x$, return $x$. Clearly $x\in A_{TM}\iff x\in A_{TM}$. Now, if $A\in L$, we need to ...


3

To your first question, the answer is affirmative: On one hand, a task that only takes polynomial time can only take polynomial space, and many among them only take linear space, so there definitely exist tasks which take linear space and polynomial time. On the other hand, that doesn't mean every task that takes linear space takes only polynomial time. ...


0

Here is an informal argument. I will leave you to fill in the gaps. If such an enhanced Turing machine (let's call it a megaTuring machine) were possible, then you could program it to accept any language (any subset of $\Gamma^*$) simply by listing the words in the language. Even a language for which a formal grammar does not exist (i.e. an unrecognizeable ...


1

Suppose we are given a language $L$ of words of finite length. We will construct machine $M_L$ that runs as the following. $M_L$ starts at state $q_0$. On input $x$ of finite length that is put to the right of its head, $M_L$ will move right all the way to the end of input, keeping the input and state intact. (This might mean nothing if the input is empty.) ...


2

Consider the word $w_n$ that is the output of $M'$ given input $n$. Note that description of $w_n$ is the description of $M'$, whose length is some constant $c$, plus the description of $n$, whose length is $O(\log n)$ since we can express $n$ in the binary representation. So $K(w_n)\le c + O(\log n)$. If $n$ is large enough, we get $$K(w_n)\lt n = |w_n|.$$...


4

The standard example is the halting problem – the language of all descriptions of Turing machines which halt on the empty input.


1

How do we know that $MIN_{\mathrm{TM}}$ is inifinite? There are infinitely many partial recursive functions (i.e., functions which are computed by TMs) and to each such function there is at least one TM which computes it and has minimal description. Why $C$ is equivalent to $D$? Because of point 3., which essentially forces $C$ and $D$ to have the same ...


0

As dkaeae indicated in his comment, a right-moving or staying Turing machine (TM) is essentially a finite deterministic automaton (FDA). Here's a proof. Let $M$ be such a machine, whose transition rules is in the form of $\delta(q, \gamma)=(t, \beta, d)$ where $q$ is the current state, $\gamma$ is the contents of the current cell, $t$ is the new state, $\...


0

Preparation Since we are talking about the exact number of steps run by a Turing machine (TM), a fixed formal definition of TM is in order. This answer assumes the popular definition of a one-tape Turing machine as in Hopcroft and Ullman (1979, p. 148). Let $N(w) \downarrow$ denote $N$ on $w$ halts eventually. Let $N(w) \uparrow$ denote $N$ on $w$ never ...


1

This inherently depends on your exact model of a TM, I'm assuming the following: A left-bounded tape, the head starts at position 0 and the word to decide is written at the tape. Furthermore, the TM has finitely many states. Now the TM can only look at the first symbol at a time, can do finite computation (i.e. can have finitely many transitions to ...


3

I had never heard about it before, but taking a quick look at it I can understand why it is considered so important. Basically, being able to prove that any program can be implemented via three basic operations (sequence, seletion, iteration) allows for simpler formalization when designing a new programming language. It's basically a one-to-one ...


3

A trivial language is one that has no strings, or one that has every string in some alphabet. In terms of models of computation, a trivial language is one that can be decided by a Turing Machine or lambda function that completely ignores its input.


0

A Turing machine moves the tape by one space per time unit. Worst case, if all moves were in the same direction, the space used would be exactly the same as the time used.


2

$\langle x \rangle$ simply denotes the encoding of some object $x$. $x$ can be a TM (e.g., its Gödel number), a string, some combination thereof (properly separated), or even other objects like a graph, etc. This serves, for instance, to distinguish between $\{ \langle M \rangle \mid \text{$M$ is a TM} \}$, which contains encodings of TMs (e.g., their Gödel ...


2

I program in Java a class Turing that takes the transitions table, the input value (to be calculated) and the initial state and simulate a Turing Machine This is not enough. You still need to prove, that your class can simulate ANY Turing machine. Normally to show Turing completness one will Implement Universal Turing Machine in this language and Show how ...


1

Suppose language $D \in NP$ and for every input $w \in D$, the certificate $y_w$ is of logarithmic length; $|y_w| = O(\log|w|)$, and a polynomial verifier $V(w,y)$ exists for $D$. We can also say: a constant $c$ exists s.t for any $w \in D$ whose certificate is $y_w$, $|y_w| \leq c \log |w|$ Consider the following algorithm $A$: Given input $x$, for every ...


2

To simplify, let’s only speak about decision problems. Decision problems have yes or no answers. For example; Is X prime? Is a decision problem. We can re-formulate the following question to be a set membership problem. We define a language L to be the set of all prime numbers, ie the set of all strings that would make the decision problem return yes. ...


18

A Turing machine cannot accept a language. A Turing Machine will either accept or reject a string or loop forever. We know it accepts the string because it will halt in an accepting state. It is said to reject a string, of it halts in a rejecting state. A TM recognises a language, if it halts and accepts all strings in that language and no others. A ...


1

An algorithm solves a problem. Let’s assume that our algorithm is made to solve problem A. The TM which implements this algorithm should halt and accept on all solutions to problem A. Due to the fact that the algorithm solves A. Let’s now define L2 as the set of all inputs that the TM halts and accepts on. This will be the set of solutions to problem A. ...


0

A Turing Machine implements an algorithm. The algorithm will either accept, reject or loop forever on certain inputs. If we collect all of the inputs that the Turing Machine halts and accepts on. This is the associated language recognised by the Turing Machine.


4

One considers two different types of Turing machines: Total Turing machines: these are machines that are guaranteed to halt on all inputs. Sometimes known as deciders. If they halt in an accepting state, then the input is accepted; otherwise it is rejected. When interested in this kind of machine, we generally define the language accepted by the machine as ...


2

A Turing machine isn't defined over a language. Given a Turing machine $M$, we can define the language of inputs on which $M$ halts; or the language of inputs which $M$ accepts; or the language of inputs which $M$ either accepts or doesn't halt on; and so on. Usually we are interested in either the language of all inputs on which $M$ halts, or (for a ...


1

As in the link provided by Raphael, Peter shows that Input Reversal requires $\Theta(n^2)$ time on vanilla single-tape TMs. For a decision problem, the language $$L = \{x0^{|x|}x \mid x \in \{0,1\}^\ast \}$$ also provably needs $\Theta(n^2)$ time to compute. To see this, use Peter's communication complexity argument , along with a classical result that $EQ_n$...


3

There are two important misunderstandings in your question. You talk about "the Turing machine" for a language but there isn't just one: in fact, if a language is recursive (or RE) then there are infinitely many Turing machines that decide (or accept) it. If a Turing machine decides a language $L$ then, by definition, it accepts every input in $L$ ...


0

Turing machines can halt or not halt. Languages cannot. The category of halting does not apply to them. We say that a language is recursive if there is a Turing machine which always halts, and accepts exactly the words in the language. It is not the language itself which always halts, but rather the Turing machine that decides it. In your case, the ...


0

Your enumerator is incorrect. Because there are infinitely many Turing machine descriptions in $G$, the loop corresponding to Line 3 will not halt, so i will never be increased. Also, Line 3.2 may not halt too. The correct enumerator is: E' = for i = 1 to infinity: Run E, the enumerator of G, to get the ith description of Turing machine <Mi> ...


4

Because, if you only use $f(n)$ tape cells, there are at most $|\Sigma|^{f(n)}$ possible strings you can have written on the tape, at most $f(n)$ different places the tape head could be, and at most $|Q|$ different states the Turing machine could be in. That means there are at most $|Q|\,f(n)\,|\Sigma|^{f(n)}$ different configurations for the machine. If ...


2

Consider all the possible configurations of a Turing machine $T$: if $S$ is the number of its states, $\Sigma$ is its alphabet, including the empty character, and $f(n)$ is an upper bound on the space used, then you only have $$ |S| \cdot f(n) \cdot |\Sigma|^{f(n)} = |S| \cdot f(n) \cdot 2^{f(n) \cdot \log_2 |\Sigma| } = 2^{O(f(n))} $$ configurations (where ...


2

Is that proof correct? Let's assume f is computable. Then I can show a TM which solves halting problem, actually even more - a TM which prints all halting TMs of given size. This TM works as following: Using blackbox for f, calculate f(n) Iterate through ALL possible TMs of input alphabet {0, 1}, states {0, 1..., n}, work alphabet {_, 0, 1, .... n} ...


0

We can enumerate all possible inputs, giving them numbers 1, 2, 3, 4, ... We can then write a program that systematically checks if one of the first n inputs is accepted in n steps, for n = 1, 2, 3 etc. This will in finite time find the input that halts. I wasn't qute sure if I would call the approach of user679128 to be "cheating" since the question was ...


0

For every Turing machine over some language L, there is a set of words that it will halt and accept on and a set of words it will halt and reject on, if it does halt. If $|L| = 1 $ then the Turing machine will accept on exactly one input. Given an arbitrary M and some input, we cannot decide whether the program will halt; halting problem. However, since M ...


3

The situation here is that we would like to a construct universal Turing machine UTM $U$ with a two-sided tape. Let $T$ be a given arbitrary Turing machine (of certain kind) that computes a partial function $f$. ($T$ is call a "program" in the question.) The question is how we will run $U$ to simulate $T$. In particular, how will we encode the input to $T$ ...


1

Here is the reduction from the halting problem, whether a given TM halts on empty input, as given in Yuval's comment. For a TM $M$, let $K$ be the same as $K$ but ignoring inputs. That is, for any input, $K$ will first erase the input so that it looks like an empty input is given. Then $K$ will simulate $M$ on empty input. When the simulation halts, $K$ ...


1

If algorithm A takes an input of size n, and has a time complexity of O(a^n) and a space complexity of O(1) First of all we do not know any exponential or sub-exponential time algorithm that requires only $O(1)$ space, having said this, it is difficult to reason about a hypothetical algorithm "A" because the spatial and temporal complexity are closely ...


2

You know that Turing machines can accept languages that aren't recursive. A linear bounded automaton (LBA) running on word $\omega$ has a finite tape at it's disposal, so the total number of configurations (tape contents, head position, state) is finite. For a given word $\omega$ you can go through all possible computations of the automaton (by the above, ...


3

A nondeterministic Turing machine can guess at most one bit each step — this is how they are defined. In particular, a nondeterministic Turing machine running in constant time can be converted to a deterministic machine also running in constant time. This should allow you to answer your own question.


2

When Hilbert set out his famous list of problems in 1900, the tenth problem was posed as follows: "Given a Diophantine equation with any number of unknown quantities and with rational integral numerical coefficients: To devise a process according to which it can be determined in a finite number of operations whether the equation is solvable in rational ...


2

The Church–Turing thesis states that every algorithm can be implemented on a Turing machine. It has stood the test of time. In particular, I believe that the answer to your question is negative. The appearance of quantum algorithms, in particular Shor's factorization algorithm, has called into question the efficient Church–Turing thesis (...


3

A linear bounded automaton is a Turing machine that runs on input of size $n$ in $\mathcal{O}(n)$ space. By the space hierachy theorem there exist languages that need e.g. $\omega(n^2)$ space.


3

We define the alphabet as the set of natural numbers. No you don't. The alphabet must be finite. Am I correct in saying that, we do not know whether this Turing machine will halt for any given input? If all you know is that the TM recognizes the language then you're correct: it could loop forever on some inputs. Since this is a decision problem, the ...


1

Let me start with a small but important point. You need to distinguish between $X$ which is a natural number and $w$ which is a string representing a natural number. So the string $11$ could represent the number $2$ in unary, the number $3$ in binary, the number $11$ in decimal, the number $17$ in hexadecimal etc. The language $L=\{w|w \text{ represents a ...


1

The Turing machine instruction table is a concrete implementation of the abstract algorithm. Usually, in one's everyday life as a computer scientist, there's not much to be gained by distinguishing these two concepts. Indeed, one can take the position that the Turing machine is the definition of "algorithm".


0

Unfortunately, when you tried to ask a general question to get hints for your homework exercise rather than the solution, you turned the question into something too general to answer. I'll try to come back at some point and write something more useful, now that you've made the question more specific. Diagonalization is the usual technique, similar to how the ...


1

The Boolean circuits you are referring to are a non-uniform model. This means that, for every input length, you have a different circuit. When we say that Boolean circuits solve a particular problem what is actually meant is that a family of circuits does, which is an infinite sequence $(C_n)_{n \in \mathbb{N}_0}$, $C_n$ being the circuit for inputs of ...


1

Consider a standard coding of Turing machine $T_0$, $T_1$, $T_2$, ... Let $b : \mathbb{N} \to \mathbb{N}$ be a non-computable bijection. Define a new coding of Turing machines $T'_n = T_{b(n)}$. Clearly, the encoding $T'$ can do everything that Turing machines can do (whatever you do with $T$ you can do with $T'$ by composing with $b$ and its inverse), but ...


2

Your thought falls short of a rigorous proof. It can hardly be considered correct intuition since it does not use the condition that each Turing machine is labelled with some number, although it does use the condition that each $k$ corresponds to a Turing machine. Your "proof" would work equally well if the condition "$M_1,M_2$,... is an enumeration of all ...


Top 50 recent answers are included