# Tag Info

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

Direct answer to the question: yes, there are esoteric and highly impractical PLs based on $\mu$-recursive functions (think Whitespace), but no practical programming language is based on $\mu$-recursive functions due to valid reasons. General recursive (i.e., $\mu$-recursive) functions are significantly less expressive than lambda calculi. Thus, they make a ...

29

Yes, it's possible. You can simulate the program by using an interpreter for the language it's written in. Now, the program (the interpreter) is fixed and the thing that used to be a self-modifying program is now the interpreter's data. In particular, you could perfectly well have a universal Turing machine that allowed the TM it's simulating to modify its ...

27

Note that Turing's proof is one of mathematics, not of physics. Within the model of a Turing machine Turing defined, undecidability of the halting problem has been proven and is a mathematical fact. Hence, Turing's proof will not 'fail' in the spacetimes, it will simply not prove anything about the relation of the halting problem and time dilation. However,...

25

Every language over a finite (or even countable) alphabet is countable. Assuming your Turing machine alphabet is finite, any language it can possibly accept is countable.

25

To expand a little on Luke's answer, physically building a neural net to solve any language requires producing electronic components with infinitely precise resistances and so on. This isn't possible, in multiple ways: You can't produce a resistor of exactly $\mathrm{2\,\Omega}$. Resistance changes with temperature and current flowing through the resistor ...

18

The Church-Turing thesis says that the informal notion of an algorithm as a sequence of instructions coincides with Turing machines. Equivalently, it says that any reasonable model of computation has the same power as Turing machines. An artificial intelligence is a computer program, i.e., an algorithm. If the Church-Turing thesis holds, then you could ...

17

First of all, quantum computers (or rather, theoretical quantum computation models), are in fact, not more powerful than Turing machines, in the sense that they can be emulated on a Turing machine and can emulate a Turing machine themselves. Note that the article itself doesn't use the word 'computable', and for a good reason. Computability isn't what they'...

16

How would you prove that the machine is faithfully simulating a brain? How would you prove that it doesn't matter if you simulate my brain or your brain or somebody else's brain? Church–Turing isn't something that can be proven. It's essentially just the statement that Turing machines correspond to the intuitive notion of algorithm and that just isn't ...

13

We can have uncountable languages only if we allow words of infinite length, see for example Omega-regular language. These languages are called $\omega$-languages. Another example will be language of subset of reals which contains, say, decimal expansions of all real numbers. There are some models in which Turing Machines are modified to accept $\omega$-...

13

There are many different meanings of the word "can". Is there an algorithm that can break AES-512 encryption? One strategy would be to take all 2^512 possible blocks of 512 bits, encrypt all of them with the public key, and for each of them check whether they match the ciphertext. In a purely abstract sense, this is an algorithm that "can" break AES-512. ...

12

All proofs of the equivalence of these two models of computation are constructive, that is they describe an algorithm for converting a program from one model of computation to the other. However, I caution you that these proofs are probably rather informal, and may not satisfy you. You may get luckier if you consult original work by computing pioneers (...

12

Every language that can implement two counters $C_1, C_2$ (i.e. two registers that can store two arbitrarily large integers) and a program made with a labeled sequence of these two elementary instructions is Turing complete: ADD $1$ to counter $C_i$, GOTO instruction $I_j$ SUBTRACT $1$ from counter $C_i$ if $C_i > 0$ and GOTO instruction $I_j$; ...

11

Your misunderstanding is: 'sure' in the sense of being computationally verified by an algorithm We are not, and we can not be . The question, Is this given Turing machine $M$ a universal one? can not be generally and algorithmically decided for the reasons you state. However, we can prove for a fixed Turing machine that it is universal -- and that ...

11

Why are oracles used in the context you mentioned (where we have an oracle for the halting problem)? Because that allows us to answer questions that are fascinating, questions like "Are there problems that are even harder than the halting problem?". I'm not saying these questions are necessarily useful or important in practice -- but they are fascinating, ...

10

Sure there is. I'm going to assume you can figure out how to convert Haskell into the lambda calculus; for a reference, look at the GHC implementation. Now just to be clear: a Turing Machine is a (finite) map from (State, Token) pairs to (State, Token, Direction) triples. We'll represent the states as integers (this is okay by the finiteness of the map) ...

10

Since you did not like Yuval's answer, you deserve this one: The equivalence of Church's $\lambda$-calculus and Turing machines is proved in the Appendix of Alan Turing's 1937 paper On computable numbers, with an application to the Entscheidungsproblem.

10

Any Turing-complete computational model that does not have modifying code (or "code") serves as a proof of that statement. I don't know that any of the standard models (TM, RAM, ...) do have modifying code, so we don't have to look too far. To get a program in whatever language you have in mind, compile from such a model (and make sure that the compiler ...

10

The Turing machine is a formal mathematical model of computation, it does not answer to any physical limitations and does not care about relativistic effects. This means that Turing's proof does not fail, since the standard definition of Turing machine does not even contain a notion of "spacetime". What you can try and do, is to define a different model of ...

9

Computer science is a science only by name. In practice, it is a blend of engineering, mathematics, and empirical science. With that out of the way, here are a few comments about the Church–Turing thesis. First, about the thesis itself. We can think of at least three interpretations of the Church–Turing thesis. Under the first, stronger interpretation, any ...

8

Turing’s proof shows that no Turing machine can solve the Halting Problem no matter how much time you give it. If your spaceship used time dilation to give a computer a billion years to work, it still might not be able to tell you anything more definite than, “Not yet.” Apparently, (Thanks, @DiscreteLizard!) if you have time travel that cannot cause ...

7

Short answer The thesis that all reasonable models of computation are polynomially-equivalent — that is, in the amount of work that they perform; whether sequentially or in parallel, albeit different by some polynomial scaling factor — is generally known as the Strong Church-Turing thesis or the Extended Church-Turing Thesis. Details The idea ...

7

Part of the issue with the idea of "proving" the Church-Turing thesis is that the Church-Turing thesis isn't a precise mathematical statement. Rather, it's the idea, or "belief" if you will, that any model of computation that could feasibly be constructed is either equal in power to a Turing machine or weaker than a Turing machine. If we were to try to ...

7

The Church-Turing thesis says that Turing machines capture precisely the effectively calculable functions from natural numbers to natural numbers. It says little about what happens when we attach a robotic arm to a computer. Any kind of machine needs to represent numbers in some way, obviously since numbers are abstract entities. A Turing machine represents ...

6

There's another possibility: hypercomputation is not implementable in the real world, and is only an imaginary/theoretical concept. If this is the case, then there is no contradiction with the Church-Turing thesis. Of course, anyone can invent imaginary worlds where strange things are true. For instance, there's the computer scientist's Superman: not only ...

6

First of all, the authors seem to be confusing two different thesis: the Church–Turing thesis and the Cook–Karp thesis. The first concerns what is computable, and the second concerns what is computable efficiently. According to the Cook–Karp thesis, all reasonable "strong" computational models are polynomially equivalent, in the sense that they all ...

6

No. A state of $n$ qubits can be represented with a vector of size $2^n$, and quantum gates can be implemented as linear operations for those vectors. Therefore a quantum computer can be simulated with a Turing machine, although with an exponential overhead. It is also known that the class of problems solvable by a quantum computer in polynomial time, BQP, ...

5

To expand a bit Luke's answer - the main question is what problems (=languages) can be solved by a computer (=TM). One might think that any problem can be solved by a computer. But this is not true. The reason is that there are such and such different Turing Machines, and way more different languages. Therefore, there must be a language that no TM can ...

5

that passage (written over a decade ago) is indeed key and invoking quite a bit of background knowledge and very well anticipating some future research directions. it is alluding to the field of hypercomputation which is sometimes at the fringes of TCS, because it studies models of computation that are supposedly "more powerful" than Turing machines. the ...

5

I'm not sure I understand your confusion (feel free to expand, if you are still confused), but there two issues that might give you better intuition: Given a Specific TM $M$, we can know for sure'' what it does for all inputs. This is not "sure" in an algorithmic way, but sure in an absolute (mathematical) way. Example: Consider the TM that has ...

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