Comment by ithinkso | Hacker News Reader

Comment by ithinkso | Hacker News Reader

Parent Full thread

You're right, maybe I do not understand because of different meaning of those words in english, which is not, in fact, my native language, but let me try explain you what I think.

From wikipedia we read:

Turing completeness

A computational system that can compute every Turing-computable function is called Turing complete (or Turing powerful). Alternatively, such a system is one that can simulate a universal Turing machine.

From the first part I think compute means that from some input A there is output B. It is later explained in 'computable function' article:

Each computable function f takes a fixed, finite number of natural numbers as arguments. Note that the functions are partial in general, i.e. they may not be defined for every possible choice of input. If a computable function is defined for a certain input, then it returns a single natural number as output (this output can be interpreted as a list of numbers using a pairing function).

So if computable function is returning something that means it halts. We are able to compute every halting algorithm in preprocessor hence it is turing complete.

Second part of this definitions says that one has to simulate turing machine (and uses the word 'alternatively' so basically it has to be the same but I can go anyway). I think that 'simulate' in this context mean 'producing same output' rather than 'doing step by step the same'. Internal tape states at certain point in time should not matter because while running they might change (or if they matter we could just return list of pair {state,time} at the end).

There is no doubt that non-halting turing machines exists but I'm not sure if that apply to this particular problem anyhow since they are not computing anything.

> Second part of this definitions says that one has to simulate turing machine (and uses the word 'alternatively' so basically it has to be the same but I can go anyway). I think that 'simulate' in this context mean 'producing same output' rather than 'doing step by step the same'. Internal tape states at certain point in time should not matter because while running they might change (or if they matter we could just return list of pair {state,time} at the end).

> There is no doubt that non-halting turing machines exists but I'm not sure if that apply to this particular problem anyhow since they are not computing anything.

The exact steps of a Turing Machine don't need to be emulated exactly, only the output needs to be the same. However, it's trivial to turn your back-and-forth example into a Turing-computable function:

Let's call your back-and-forth machine "M1" and, without loss of generality, let's say it starts at cell 0, moves to cell 1, then back to cell 0. We can then define a new machine "M2" which outputs a list of M1's head positions at each step, based on a direct simulation of M1. In other words, M2 will output 01010101010101.... forever, never halting.

The C preprocessor cannot simulate M2, precisely because it cannot simulate M1.

Also, note that we don't need to wait for a Turing machine to halt before we read its output. There are many useful programs which should not halt, like servers and operating systems.

> I think that 'simulate' in this context mean 'producing same output' rather than 'doing step by step the same'.

That is correct. But "producing the same output" means not halting when a TM does not halt. Otherwise it is not the same output.

But halting is actually a red herring in this case. Because the number of states that a cpp-machine can visit is finite, it is easy to construct a TM (or even an FSM) that halts on all inputs but produces a different output than any given cpp machine for some input. For example, a TM can do bignum arithmetic that halts on all inputs, but for some input it must be the case that such a TM will produce a different output than any given FSM, and hence any given cpp-machine, since cpp-machines are strictly less powerful than FSMs.

Reply on news.ycombinator.com