# Tag Info

232

Because a lot of really practical problems are the halting problem in disguise. A solution to them solves the halting problem. You want a compiler that finds the fastest possible machine code for a given program? Actually the halting problem. You have JavaScript, with some variables at a high security levels, and some at a low security level. You want to ...

86

Humans can solve some instances of that problem efficiently, but there is no reason to believe that humans can solve all instances efficiently. Showing one instance that a human can solve efficiently does not imply that humans can solve all instances efficiently. Undecidable means "there is no algorithm that can solve all instances and that always ...

75

The claim is not that a computer cannot determine the validity of some mathematical statements. Rather, the claim is that there is a class $\mathcal{C}$ of mathematical statements such that no algorithm can decide, given a statement from class $\mathcal{C}$, whether it is valid or not. The standard choice for the class $\mathcal{C}$ is statements about ...

70

Turing complete languages can compute the same set of functions $\mathbb{N}^k \rightarrow \mathbb{N}$, which is the set of general recursive partial functions. That's it. This says nothing about the language features. A Turing Machine has very limited compositional features. The untyped $\lambda$-calculus is far more compositional, but lacks many features ...

58

Before I answer your general question, let me first take a step back, give some history background, and answer a preliminary question: Do non-computable functions even exist? [notational note: we can relate any function $f$ with a language $L_f=\{ (x,y) \mid y=f(x) \}$ and then discuss the decidability of $L_f$ rather than the computability of $f$] ...

57

It all comes from undecidability of the halting problem. Suppose we have a "perfect" dead code function, some Turing Machine M, and some input string x, and a procedure that looks something like this: Run M on input x; print "Finished running input"; If M runs forever, then we delete the print statement, since we will never reach it. If M doesn't run ...

57

TLDR; this is possible but not practical. (assuming the translator has access to the requisite libraries)? This ends up being the tricky bit, and is part of why things like this don't end up being used in practice. All compilers are translators. Translating from one language to another is definitely possible, and this is literally all a compiler is ...

55

Idris is Turing Complete! It does check for totality (termination when programming with data, productivity when programming with codata) but doesn't require that everything is total. Interestingly, having data and codata is enough to model Turing Completeness since you can write a monad for partial functions. I did this, years ago, in Coq - it's probably ...

55

Turing-completeness says one thing and one thing only: a model of computation is Turing-complete, if any computation that can be modeled by a Turing Machine can also be modeled by that model. So, what are the computations a Turing Machine can model? Well, first and foremost, Alan Turing and all of his colleagues were only ever interested in functions on ...

54

It's possible to replace recursion by iteration plus unbounded memory. If you only have iteration (say, while loops) and a finite amount of memory, then all you have is a finite automaton. With a finite amount of memory, the computation has a finite number of possible steps, so it's possible to simulate them all with a finite automaton. Having unbounded ...

53

In practical terms, it is important because it allows you to tell your ignorant bosses "what you're asking is mathematically impossible". The halting problem and various NP-complete problems (e.g. the traveling salesman problem) come up a lot in the form of "Why can't you just make a program that does X?", and you need to be able to give an explanation of ...

52

You already have a representation of that function as text. Convert each character to a one-byte value using the ASCII encoding. Then the result is a sequence of bytes, i.e., a sequence of bits, i.e., a string over the alphabet $\{0,1\}^*$. That's one example encoding.

48

Turing completeness is an abstract concept of computability. If a language is Turing complete, then it is capable of doing any computation that any other Turing complete language can do. This does not, however, say how convenient it is to do so. Some features that are easy in some languages may be very difficult in others, due to design choices. Turing ...

47

You can use the algorithm which detects whether a linked list loops to implement the Halting Function with space complexity of O(1). To do that, you need to store at least two copies of the partial state of the program in memory, plus the overhead of the checking program. So on a given computer, you cannot test all programs that can execute on that computer,...

46

No, it's still consistent with the Church-Turing thesis, their model comes equipped with genuine real numbers (as in arbitrary elements of $\mathbb{R}$), which pretty much immediately extends the power beyond that of a Turing Machine. In fact, the title of 1.2.2 is "The meaning of (non computable) real weight", where they discuss why their model is built to ...

45

A pretty simple example could be a program testing the Collatz conjecture: $$f(n) = \begin{cases} \text{HALT}, &\text{if n is 1} \\ f(n/2), & \text{if n is even} \\ f(3n+1), & \text{if n is odd} \end{cases}$$ It's known to halt for $n$ up to at least $5 × 2^{60} ≈ 5.764 × 10^{18}$, but in general it's an open problem.

45

Yes, there are theoretical machines which exceed the Turing machines in computational power, such as Oracle machines and Infinite time Turing machines. The buzzword that you should feed to Google is hypercomputation.

45

The most naive and simple answer to your question is that the code provided (and compiled machine code) are in-fact represented as syntactic strings of {0,1}*. Additionally, since you are talking about turing machines, the programs they run are a linear list of operations/instructions, there is no reason these cannot be represented as bits/bytes.

40

Ignore the picture for a moment; we'll get to it shortly. The program $H(a, b)$ is supposed to be a halt tester: when we give $H$ an input of a program $a$ (think of $a$ as the listing of a program) and anything at all for $b$, $H(a, b)$ acts as follows If the program represented by $a$ halts when given $b$ as input, $H(a, b)$ will answer "yes". On the ...

39

While it is true that the computation of a quantum Turing machine is vastly different from that of a classical one, nevertheless quantum Turing machines can be simulated on a classical Turing machine, albeit with exponential slowdown. In particular, everything that can be computed on a quantum Turing machine can also be computed on a classical Turing machine....

36

I'm not sure but I think the answer is no, for rather subtle reasons. I asked on Theoretical Computer Science a few years ago and didn't get an answer that goes beyond what I'll present here. In most programming languages, you can simulate a Turing machine by: simulating the finite automaton with a program that uses a finite amount of memory; simulating ...

34

Every recursion can be converted to iteration, as witnessed by your CPU, which executes arbitrary programs using a fetch-execute infinite iteration. This is a form of the Böhm-Jacopini theorem. Moreover, many Turing-complete models of computation have no recursion, for example Turing machines and counter machines. Primitive recursive functions correspond to ...

33

The halting problem states there is no algorithm that will determine if a given program halts. As a consequence, there should be programs about which we can not tell whether they terminate or not. "We" are not an algorithm =) There is no general algorithm that could determine if a given program halts for every program. What are the simplest (smallest) ...

32

I can't resist... ⡂⡀⣀⢀⣄⡀⣰⡉⡀⠀⡀⡀⣀⠀⢀⣀⢀⣄⡀⡂⢀⣀⡀⢀⢀⡀⠀⡰⣀⠀⣀⠀⡂⡀⣀⢀⣄⡰⡀⢠⠂ ⡇⡏⠀⡇⡇⠀⢸⠀⡇⢀⡇⡏⠀⡇⣏⠀⠀⡇⠀⡇⣏⠀⣹⢸⠁⢸⠀⡇⢈⠷⡁⠀⡇⡏⠀⡇⡇⠀⡇⢼⠀ ⠁⠁⠀⠁⠈⠁⠈⠀⠈⠁⠁⠁⠀⠁⠈⠉⠀⠈⠁⠁⠈⠉⠁⠈⠀⠈⠀⠱⠉⠀⠉⠀⠁⠁⠀⠁⠈⠱⠁⠘⠄ ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀ ⠀⠀⠀⢤⡀⡤⠀⣀⣀⣀⠀⢤⡀⡤⠀⠀⢰⠀⠀⢹⠠⠀ ⠀⠀⠀⣠⠛⣄⠀⠒⠒⠒⠀⣠⠛⣄⠀⠉⢹⠉⠁⢸⢀⠀ ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠘⠀ ⠀⠀⠀⣄⢄⠤⢄⢴⠤⢠⠀⢠⢠⡠⢠⡠⢄⠀⢤⡀⡤⢺⡖⠐⣷⠂⠊⢉⡆ ⠀⠀⠀⡇⠸⣍⣉⠸⣀⠸⣀⢼⢸⠀⢸⠀⢸⠀⣠⠛⣄⠀⠀⠀⠀⠀⣴⣋⡀ ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀ ⢱⠀ ⢸⠁ ⠊ (The ...

31

It seems to me that the Halting Problem is nothing more than a so called "paradox," a self referencing (at the very least cyclical) contradiction in the same way as the Liar's paradox. The only conclusion it makes is that the Halting Function is susceptible to such malformed questions No, that's not what the halting problem is about. Paradoxes like the liar'...

31

Consider the real number encoding of the (almost) halting problem, i.e. $0.r_1r_2...$ where $r_i=1$ if the i'th Turing machine (relative to the lexicographic ordering) halts on the empty input, and $r_i=0$ otherwise. Let us denote this number by $R$. Now, consider the machine $M$ which on input $n$ simulates all Turing machines of length $< n$ on the ...

30

The Church–Turing thesis (in one formulation) states that everything that can be physically computable can also be computed on a Turing machine. Assuming you believe this theses, and given that you're interested in functions which such machines could compute (and not in, say, interactive computation), then no hypercomputation is possible. The Church&...

30

Mathematicians and philosophers often assume that machines (and here, he probably means "computers") cannot surprise us. This is because they assume that once we learn some fact, we immediately understand every consequence of this fact. This is often a useful assumption, but it's easy to forget that it's false. He's saying that systems with simple, finite ...

30

The correct version of the claim states that every computable language is accepted by infinitely many Turing machines. Indeed, if $L$ is computable, then there is a Turing machine $T$ that accepts it. Let $T_n$ be $T$ together with $n$ unreachable states. Then $T_n$ also accepts $L$, and the machines $T_n$ are all different from one another.

Only top voted, non community-wiki answers of a minimum length are eligible