The long lost manual for the Zuse Z4 has been found • Hacker News Board

Re: The long lost manual for the Zuse Z4 has been found

#61

Post by cameldrv » Mon, Sep 28, 2020, 5:45 PM UTC

codeflo wrote: post #23

7373737373 wrote: post #13

Earlier quoted context omitted.

The proof that the Z3 is turing complete is pretty funny: https://news.ycombinator.com/item?id=1945455 http://www.inf.fu-berlin.de/inst/ag-ki/rojas_home/documents/...

I knew that there was a proof, but never read the paper before. Now that I did, I think that proof is garbage tbh. For Turing completeness, a fixed, constant-sized program needs to be able to handle arbitrary inputs and use arbitrary amounts of memory. It's important to distinguish the model from the implementation here. Theoretically, a language like Python is Turing complete. (And BTW you don't need infinite precis…

Ultimately there is no real computer that is Turing complete, because all real computers are finite. Ultimately, you can represent any real computer with a (very large) DFA.

The two things missing from what would normally be considered a universal computer are conditionals and indirect addressing. The Z3 is also limited in that it executes a specific finite set of instructions in linear order, with no branching.

In the proof, they get around the finite length of a program by literally creating a loop -- they glue one end of the paper tape of the program to the other so that the computer can keep executing the same instruction stream forever. Then they get around the lack of indirect addressing by accessing every memory location in every loop. I agree that it's very much a stretch to call the Z3 Turing complete.

Re: The long lost manual for the Zuse Z4 has been found

#62

Post by MrBuddyCasino » Mon, Sep 28, 2020, 6:23 PM UTC

formerly_proven wrote: post #30

I just recently learned just how underappreciated Zuse is. Besides the Z3 and Z4 being hugely modern machines while _also_ being the first programmable computers (load/store architecture, fixed length instructions, multiple stage execution with overlapping stages, 32-bit float [which he independently invented, but was previously discovered, but not implemented, once in 1914], branch delay slots), he suggested the str…

„ Zuse is the nerd's nerd. Not only did he build the first programmable computer, he also was the first dude to grok digital physics and the idea that the universe may be a computer. Zuse's book 'Calculating Space' was written in the 60s, years before Fredkin et al. People thought he was insane. Consequently, he thought his intellectual life was over and actually went into startups later in life. Today, his ideas about the universe being computation are very trendy. Before his death, he was invited out to MIT and shown some love for his pioneering work.“ [0]

[0] https://news.ycombinator.com/item?id=9200896

Re: The long lost manual for the Zuse Z4 has been found

#63

Post by formerly_proven » Tue, Sep 29, 2020, 10:21 AM UTC

cameldrv wrote: post #61

codeflo wrote: post #23

Earlier quoted context omitted.

I knew that there was a proof, but never read the paper before. Now that I did, I think that proof is garbage tbh. For Turing completeness, a fixed, constant-sized program needs to be able to handle arbitrary inputs and use arbitrary amounts of memory. It's important to distinguish the model from the implementation here. Theoretically, a language like Python is Turing complete. (And BTW you don't need infinite precis…

Ultimately there is no real computer that is Turing complete, because all real computers are finite. Ultimately, you can represent any real computer with a (very large) DFA. The two things missing from what would normally be considered a universal computer are conditionals and indirect addressing. The Z3 is also limited in that it executes a specific finite set of instructions in linear order, with no branching. In t…

Wouldn't a DFA for a computer have to have 2^n states for n bits of memory, so it's size would be exponential to memory size of the computer? So even for a pedestrian 640K of memory, that's like 10^10^7 states. Sounds a lot like trying to simulate a non-deterministic Turing machine on a deterministic machine; the state space explodes exponentially making it intractable.