Hacker News Reader

HNHacker News

Top New Best Ask Show Jobs

Comment by mdonahoe | Hacker News Reader

Parent Full thread

mdonahoe·

If we had that, how many n64 implementations could we stack?

More generally, what’s the most nested Turing machine ever built?

View on HN

You might love this article from page 14 of PoC||GTFO #20:

https://www.alchemistowl.org/pocorgtfo/pocorgtfo20.pdf

(warning: it's a relatively big PDF file, which also works as a .zip file with resources)

Zero. No Turing machine has ever been built. The tape needs to be infinite to be a Turing machine.

GP probably meant something among the lines of: "What is the most nested turing complete system ever built"

You are correct, this is what I meant.

I've found "self-interpreter" implementations that aim to be short

https://arxiv.org/html/cs/0311032

https://codegolf.stackexchange.com/questions/585/self-interp...

But I haven't found anyone yet that optimized for actual number of recursive implementations on a real machine.

Can you prove that statement in finite time?

What's the problem with adding more tape as needed? You don't need a literally infinite tape to have infinite tape from the machine's POV.

Linux already overcommits memory so much you can imaging it's infinite, the big show-stopper is the 64 bit integers used to track it. We'd need infinite pointer sizes before we could meaningfully use infinite tape.

Good thing is there is no halting problem when using 64bit pointers.

Turing machines don't have pointers, just offsets from the current position. Since you can't move infinite steps, you can still use finite offsets.

Reply on news.ycombinator.com