Hacker News Reader

Comment by javajosh | Hacker News Reader

Okay I'll volunteer to be the dummy who says I don't get it. The cell of a Turing tape can contain an arbitrary number? The head of Turing machine can add?? I think my underlying assumptions have been violated, which means either I have something interesting to learn or this is a bad result. Probably the former.

View on HN

There are many ways to define Turing Machines:

* only binary alphabet, or allow any finite alphabet on the tape(s)

* tape is infinite in a single direction or in both (and various possibilities as to how to handle reaching the edge)

* there is one tape or there are more

* the head has to move every time, or can it remain on the same cell

* etc.

And they are all equivalent in terms of computability (ie. they can compute the same functions), and mostly equivalent in terms of algorithmic complexity (ie. they take the same time to run, up to a polynomial).

So almost no one bothers actually saying which model they use, unless they are doing a rigorous proof.

However, when papers like this one say "Hey, let's take my favorite model of Turing Machines and restrict it so that [X]", then the results highly depends on what their favorite model is. Except they don't always bother saying which one it is.

For example, if you restrict yourself to Turing Machines with a single state, two tapes, and any alphabet allowed on at least one of the tapes, then it's enough to emulate any one-tape Turing machine, simply by writing the state on a single cell of the second tape and repeatedly read it. Which in turn are known to be able to emulate any conventional model of Turing Machines.

Looking at the first page of the linked PDF, it's not explicit about whether the alphabet must be finite, although it's implied by the summary saying that addition can only be done modulo some finite value.

It is explicit about having an arbitrary alphabet, a single tape that's infinite in both directions and that the head has to move every time.

I don't think I've ever seen anyone restrict a Turing machine in a novel way and not follow that up with a rigorous proof.

Not arbitrary. Modulo some constant k, the size of the tape alphabet. They're just choosing as the tape alphabet the set { 1, 2, …, k-1 }, and as the transition function one that maps each n to n+1 mod k. It's just a lookup table.

The transition function can only do modular addition within a cell, but the paper also describes how to build a k-ary counter.

If your single state has the increment lookup table for a single cell, you just need to move to the next cell to do carries, and move to the previous cell to leave the counter when you're done. A special carry character is written instead of zero to make sure you leave the whole counter, and you convert it to zeroes as you leave.

In the Turing machine formalism that was taught at my university(1), the set of symbols that can be stored in a cell must be finite, but can otherwise be anything needed to solve the problem at hand. For each state in the associated state machine, there’s effectively a lookup table that maps the current tape symbol to some other, and an instruction about how to move the tape head for the next step.

This means, in particular, that you can annotate symbols on the tape by having different variants of each input symbol, so long as the number of variants is strictly bounded.

(1) There are many equally-powerful variants, so there’s no guarantee that others will be working with the same definition.

The tape cannot contain arbitrary numbers, but symbols from any finite alphabet, which can be int256_t, and the transition function can be any partial function on pairs of tape symbols and input states.

INPUT: can? "contain an arbitrary..." & ifnot= "something interesting to learn"

OUTPUT: https://en.m.wikipedia.org/wiki/Arbitrariness#See_also

#~~

(trying to scratch together code you can run that'll answer your question.. hm, the initial function is untyped without a better sense of 'number'.)

Reply on news.ycombinator.com