Hacker News new | ask | show | jobs
by pclmulqdq 643 days ago
A computer is technically not a Turing machine due to the lack of infinite RAM. It is a finite state machine with an absurdly large state space.
3 comments

I've always interpreted the definition of storage as arbitrarily large, not specifically infinite. The universe, after all, is finite. The "well, acshually" arguments aren't interesting, because they're 100% abstract.
It is defined as arbitrarily large but not infinite. That's not because of physical concerns, but because some of the theorems don't work if the memory is actually infinite.
You're comparing an a priori concept with a posteriori one. It's like claiming the number five doesn't "acshually" exist. Like yea, it's a concept, concepts don't exist.

A universe isn't a turing machine because it can't run all the programs that can run on a turing machine. This isn't exactly controversial.

What's the difference between arbitrary large and infinite? Would you say the number of possible Turing computable functions is merely arbitrary large and not actually infinite?
There is a very clear distinction: one is finite the other is infinite

If you only allow arbitrary large turning machines, there is a fixed number of programs which can run

When you're talking about something like neural networks on a 4004, the "well ackshually" argument does become very much relevant. The limitations of that kind of platform are hard enough that they do not approximate a Turing machine with respect to modern software.
Running Linux on a 4004 is possible, as we've seen, but running llama is just way too far? Interesting take.
Llama takes a lot more MIPS and a lot more RAM than linux. Linux is more complicated, but computers were running linux 30 years ago. In this case, quantity has a quality all of its own.
It takes 14,493,515,821 cycles to boot Alpine Linux in an qemu.

    perf stat -Bddd qemu-system-x86_64   -m 2048   -cdrom alpine.iso   -boot d   -enable-kvm   -cpu host   -smp 2   -net nic -net user,hostfwd=tcp::2222-:22   -nographic   -serial mon:stdio   -monitor telnet:127.0.0.1:1234,server,nowait   -d in_asm,cpu   -D qemu.log
It takes 1,927,757,029,221 cycles to summarize a 1625 token Dijkstra essay with LLaMA 8B.

    perf stat -Bddd llamafile -m Meta-Llama-3.1-8B-Instruct.BF16.gguf -f ~/prompt1625.txt -c 4096 -n 40
Ignoring things like AVX512 you're looking at about 100x more compute to do something serious with LLaMA.

However! If you just want to demo it working, then you could generate 4 tokens using TinyLLaMA 1.1B which takes 25,164,386,466 cycles. That's about the same cost as booting Linux. So you could do TinyLLaMA if you can do Linux.

That's closer than I thought, to be honest.

Note also that the 4004 lacks a floating-point unit of any kind - not just a vector unit. I think people make 8-bit integer quantizations of LLMs, though, which would be the fastest versions to run on a 4004.

Because it has infinite RAM, technically the Turing machine is not a machine.
What? A Turing machine can literally be built. The only problem is supplying the infinite tape, or splicing on more when it runs to the end of a finite tape.

Machines that address storage using fixed width pointers (and have no other kind of storage) cannot be Turing machines.

The only problem is supplying the infinite tape

In so far as infinite tape is feasibile, you are correct.

Any useful TM program halts, so you need finite tape. Only figuring out beforehand how much will you need is difficult.
You don't want your telephone exchange to halt. That's why the engineering marvel Erlang. "Engineering" being the key word. The Halting problem isn't a real problem. Just pull the power cord.
You want every call handled in finite time. It's not that there is an unending computation in a telephone exchange, but a series of finite tasks. You can call it corecursion, coinduction or something else co-.
Can’t any computer with external connectivity (ie serial or network connectivity) be considered to have infinite memory?
A computer with external connectivity to a tape machine capable of reading and writing a symbols and moving along the tape would qualify as a Turing machine, provided someone feeds it enough tape for any problem that's thrown at it.
How would that work?
"we're the dot in dot.com"

No wait ... the other one ...

"the network is the computer"

It was funny when Sun proudly and unilaterally proclaimed that Sun put the "dot" into "dot com", leaving it wide open for Microsoft to slyly counter that oh yeah, well Microsoft put the "COM" into "dot com" -- i.e. ActiveX, IE, MSJVM, IIS, OLE, Visual Basic, Excel, Word, etc!

And then IBM mocked "When they put the dot into dot-com, they forgot how they were going to connect the dots," after sassily rolling out Eclipse just to cast a dark shadow on Java. Badoom psssh!

https://www.itbusiness.ca/news/ibm-brings-on-demand-computin...

"The Network Is The Network and The Computer Is The Computer. We regret the confusion."

https://news.ycombinator.com/item?id=34256623

>Oh yeah, don't get me started about NFS! (Oops, too late.) I'll just link with short summaries: [...]

>NFS originally stood for "No File Security". [...]

>The network is the computer is insecure, indeed.