Dane oryginału: Feynman lectures on computation. Richard P. Feynman. Edited by Tony Hey, Robin W. Allen. Published 2018 by CRC Press. Firts published 1996 by Westview Press. All Rights Reserved. Authorised translation from the English language edition published by CRC Press, a member of the Taylor & Francis Group LLC.

Tłumacz: Małgorzata Dąbkowska Kowalik i Witold Sikorski

Projekt okładki: Agnieszka Machnicka

Opracowanie graficzne okładki: Przemysław Spiechowski

Wydawca: Karol Zawadzki

Koordynator ds. redakcji: Adam Kowalski

Redaktor: Izabela Mika

Produkcja: Mariola Grzywacka

Skład wersji elektronicznej na zlecenie Wydawnictwo Naukowe PWN Michał Latusek

Książka, którą nabyłeś, jest dziełem twórcy i wydawcy. Prosimy, abyś przestrzegał praw, jakie im przysługują. Jej zawartość możesz udostępnić nieodpłatnie osobom bliskim lub osobiście znanym. Ale nie publikuj jej w internecie. Jeśli cytujesz jej fragmenty, nie zmieniaj ich treści i koniecznie zaznacz, czyje to dzieło. A kopiując jej część, rób to jedynie na użytek osobisty.

Szanujmy cudzą własność i prawo

Więcej na www.legalnakultura.pl

Polska Izba Książki

eBook został przygotowany na podstawie wydania papierowego z 2022r. (Wydanie I)

Warszawa 2022

Copyright wydania polskiego © by Wydawnictwo Naukowe PWN SA

Warszawa 2022

ISBN: 978-83-01-22190-4

Wydawnictwo Naukowe PWN SA

02-460 Warszawa, ul. Gottlieba Daimlera 2

tel. 22 69 54 321; faks 22 69 54 288; infolinia 801 33 33 88

e-mail: pwn@pwn.com.pl; reklama@pwn.pl

www.pwn.pl

Bezpłatny fragment

Przedmowa Wydawcy

Przedmowa Feynmana

1. Wprowadzenie do komputerów

1.1. Model urzędnika archiwisty

1.2. Zbiory instrukcji

1.3. Podsumowanie

2. Organizacja komputerów

2.1. Bramki i układ kombinacyjny

2.2. Dekoder binarny

2.3. Więcej o bramkach: bramki odwracalne

2.4. Funkcjonalnie pełne zbiory operatorów

2.5. Przełączniki i pamięć komputerowa

2.6. Taktowanie i rejestry przesuwne

3. Teoria obliczeń

3.1. Efektywne procedury i obliczalność

3.2. Automaty skończone

3.3. Ograniczenia automatów skończonych

3.4. Maszyny Turinga

3.5. Więcej o maszynach Turinga

3.6. Uniwersalne maszyny Turinga i problem stopu

3.7. Obliczalność

4. Kodowanie i teoria informacji

4.1. Informatyka i teoria komunikacji

4.2. Wykrywanie błędów i kody korygujące

4.2.1. Sprawdzanie parzystości

4.2.2. Kody Hamminga

4.2.3. Uwaga o pamięci

4.3. Twierdzenie Shannona

4.4. Geometria przestrzeni komunikatów

4.5. Kompresja danych i informacja

4.6. Teoria informacji

4.7. Dalsze techniki kodowania

4.7.1. Kodowanie Huffmana

4.7.2. Kodowanie predykcyjne

4.8. Transmisja sygnałów analogowych

5. Odwracalne obliczenia i termodynamika obliczeń

5.1. Fizyka informacji

5.1.1. Demon Maxwella i termodynamika pomiarów

5.1.2. Energia i teoria Shannona

5.2. Odwracalne obliczenia i termodynamika obliczeń

5.2.1. Komputery odwracalne

5.2.2. Obliczanie kopii

5.2.3. Implementacja fizyczna

5.2.4. Żyjący komputer

5.3. Obliczenia: koszty energii a prędkość

5.4. Ogólny odwracalny komputer

5.5. Komputer z kulą bilardową

5.6. Obliczenia kwantowe

6. Komputery mechaniki kwantowej

6.1. Wprowadzenie

6.2. Obliczenia z wykorzystaniem maszyn odwracalnych

6.3. Komputer mechaniki kwantowej

6.4. Niedoskonałości i nieodwracalna strata energii swobodnej

6.5. Upraszczanie implementacji

6.6. Wnioski

6.7. Bibliografia

7. Fizyczne aspekty obliczeń

Zastrzeżenie od wydawców

7.1. Fizyka przyrządów półprzewodnikowych

7.1.1. Dioda ze złączem p-n oraz tranzystor n-p-n

7.1.2. MOSFET

7.1.3. Bramki logiczne MOSFET i elementy obwodu

7.2. Zużycie energii i utrata ciepła w komputerach

7.2.1. Inwerter CMOS

7.2.2. Gorące taktowanie

7.2.3. Ogólne rozważania i interesujące związki

7.3. Budowa układu VLSI

7.3.1. Planarna technologia produkcji procesorów

7.3.2. Projekt obwodu i tranzystory przepustowe

7.3.3. Programowane macierze logiczne

7.4. Dalsze ograniczenia projektu maszyny

7.4.1. Przesunięcie czasowe

7.4.2. Pakowanie przewodów: reguła Renta

Posłowie: wspomnienie o Richardzie Feynmanie

Polecane lektury

Rozdziały 1, 2 i 3

Rozdział 4

Rozdział 5

Rozdział 6

Rozdział 7

Przypisy

Przedmowa Wydawcy

Ponieważ minęło już jakieś osiem lat od śmierci Feynmana[1], czuje się w obowiązku wyjaśnić genezę tej książki – Feynmana wykłady. Przetwarzanie informacji. W listopadzie 1987 roku odebrałem od Helen Tuck, wieloletniej sekretarki Feynmana, telefon z informacją, że Feynman chce, abym spisał do publikacji jego notatki z wykładów na temat obliczeń. Szesnaście lat wcześniej, na stażu podoktorskim w CalTechu, odrzuciłem możliwość redagowania jego wykładów „Parton”, twierdząc, że odciągnie to uwagę od moich badań. Często żałowałem tej decyzji, więc nie trzeba było mnie długo namawiać, abym tym razem spróbował. W CalTechu początkowo zajmowałem się fizyką cząstek elementarnych, ale dziesięć lat później, podczas wizyty na urlopie naukowym w CalTechu w 1981 roku, zainteresowałem się problemami fizyki obliczeniowej – bawiąc się podejściami wariacyjnymi, które (jak się później dowiedziałem) były podobne do technik stosowanych przez Feynmana wiele lat wcześniej. Bodziec w postaci seminarium naukowego w CalTech na temat „Przyszłości VLSI”, zorganizowanego przez Carvera Meada, zapoczątkował mój zwrot w kierunku obliczeń równoległych i informatyki.

Feynman interesował się problematyką obliczeń od wielu lat, od czasu Projektu Manhattan i modelowania plutonowej bomby implozyjnej. W „Los Alamos z dołu”, opublikowanym w Pan raczy żartować, panie Feynman! [2], Feynman wspomina, jak powierzono mu kierowanie „grupą IBM”, której zadaniem było obliczenie energii uwalnianej podczas implozji. Nawet w tamtych czasach, przed pojawieniem się komputera cyfrowego, Feynman i jego zespół opracowali sposoby równoległego wykonywania obliczeń bomb. W oficjalnych zapiskach CalTechu Feynman figuruje jako osoba, która w 1981 roku wraz z Johnem Hopfieldem i Carverem Meadem prowadziła interdyscyplinarny kurs zatytułowany „Fizyka obliczeń”. Kurs był prowadzony przez dwa lata i John Hopfield pamięta, że cała trójka nigdy nie zdołała poprowadzić go razem w tym samym roku: w jednym roku Feynman był chory, a w drugim Mead był na urlopie. Notatka z kursu 1982/1983 ujawnia jego charakter: podstawowy elementarz na temat obliczeń, obliczalności i teorii informacji, po którym następuje część zatytułowana „Granice obliczeń pojawiające się w świecie fizycznym i «fundamentalne» granice obliczeń”. Wykłady w tym roku prowadzili Feynman i Hopfield, a gościnnie wystąpili tacy eksperci, jak Marvin Minsky, John Cocke i Charles Bennett. Wiosną 1983 roku, dzięki powiązaniom z MIT i za sprawą swojego syna Carla, Feynman pracował jako konsultant Danny’ego Hillisa w Thinking Machines, ambitnej, nowej firmie zajmującej się komputerami równoległymi.

Jesienią 1983 roku Feynman po raz pierwszy samodzielnie prowadził kurs na temat obliczeń, który w dokumentacji CalTechu nosi tytuł „Możliwości i ograniczenia maszyn obliczeniowych” [3]. W latach 1984/1985 i 1985/1986 wykłady były nagrywane na taśmy i to właśnie z tych taśm oraz notatników Feynmana zrekonstruowano niniejsze notatki z wykładów. Odpowiadając Helen Tuck, powiedziałem, że odwiedziłem CalTech w styczniu 1988 roku, aby wygłosić wykład na „Hypercube Conference”. Była to konferencja poświęcona obliczeniom równoległym, której podwalinami były pionierskie prace Geoffreya Foxa i Chucka Seitza w CalTech nad ich komputerem równoległym „Cosmic Cube”. Rozmawiałem z Feynmanem w styczniu i bardzo chciał, aby jego wykłady na temat obliczeń ujrzały światło dzienne. Zgodziłem się podjąć tego projektu i przed moim powrotem do Southampton ustaliliśmy, że będziemy w kontakcie. Niestety Feynman zmarł niedługo po tym spotkaniu i nie mieliśmy szansy na bardziej szczegółową rozmowę na temat proponowanej treści jego opublikowanych wykładów.

Helen Tuck przekazała mi zarówno kopie taśm, jak i kopie notatek Feynmana z tego kursu. Ułożenie jego wykładów w formę nadającą się do publikacji okazało się być bardzo pracochłonne. Przekazane mi materiały, podobnie jak w przypadku wcześniejszego kursu z Hopfieldem i Meadem, obejmowały kilka wykładów wygłoszonych przez zaproszonych prelegentów na tematy od języka programowania „Scheme” do zastosowań fizyki w „Cosmic Cube”. Odkryłem też, że kilka osób próbowało wykonać tę pracę przede mną! Jednak podstawowy wkład Feynmana w kurs szybko stał się jasny – rozdział wprowadzający o komputerach, po którym następuje pięć rozdziałów dotyczących analizy ograniczeń komputerów wynikających ze struktury bramek logicznych, z logiki matematycznej, z zawodności komponentów komputerów, z termodynamiki obliczeń i z fizyki technologii półprzewodników. W szóstym rozdziale Feynman omówił ograniczenia komputerów wynikające z mechaniki kwantowej. Jego analiza komputerów kwantowych została przedstawiona na spotkaniu w Anaheim w czerwcu 1984 roku, a następnie opublikowana w czasopiśmie Optics News w lutym 1985 roku. Po tych fragmentach następowały wykłady zaproszonych prelegentów na temat szerokiego zakresu „zaawansowanych zastosowań” komputerów – robotyki, sztucznej inteligencji, wizji, architektur równoległych i wielu innych tematów, które zmieniały się z roku na rok.

Zgodnie z zapowiedzią wykład Feynmana miał na celu przedstawienie ograniczeń i możliwości komputerów. Chociaż wykłady zostały wygłoszone jakieś dziesięć lat temu[4], większość materiału jest stosunkowo „ponadczasowa” i stanowi Feynmanowski przegląd niektórych standardowych tematów z dziedziny informatyki. Jako całość kurs jest niezwykły i prawdziwie interdyscyplinarny. Poza tym że ukazuje „podejście Feynmana” do takich tematów, jak obliczalność, maszyny Turinga (lub jak mówi Feynman, „maszyny Pana Turinga”), twierdzenie Shannona i teoria informacji, zawiera też jego rozważania na temat obliczeń odwracalnych, termodynamiki i obliczeń kwantowych. Tak szeroko zakrojone omówienie fundamentalnych podstaw komputerów jest niewątpliwie wyjątkowe i stanowi Feynmanowskie spojrzenie „z boku” na całość nauki o obliczeniach. Nie oznacza to, że wszystkie aspekty tych zagadnień są tu omówione, gdyż wiele zostało pominiętych – jak choćby języki programowania i systemy operacyjne. Niemniej jednak wykłady te stanowią podsumowanie naszej wiedzy na temat prawdziwie fundamentalnych ograniczeń komputerów cyfrowych. Feynman nie był zawodowym informatykiem i bardzo szybko omawia dużą ilość materiału, kładąc nacisk raczej na sprawy zasadnicze niż na zgłębianie szczegółów. Jednak jego podejście do tematu jest zdecydowanie praktyczne i jest to podkreślone przez jego decyzje, aby temat teorii obliczalności przedstawić, rozważając maszyny Turinga. Feynman czerpie oczywistą przyjemność z wyjaśniania, jak coś pozornie tak prostego jak maszyna Turinga może prowadzić do tak doniosłych wniosków. Jego filozofia uczenia się i odkrywania również mocno przebija się w tych wykładach. Feynman nieustannie podkreśla, jak istotne są samodzielne próby rozwiązywania problemów, zanim zajrzy się do książki, by zobaczyć, jak zrobili to „eksperci”. Wykłady te dają niepowtarzalny wgląd w sposób pracy Feynmana.

W niektórych miejscach skorzystałem z praw wydawcy w sposób, który powinienem teraz wyjaśnić. Gdzieniegdzie znajdują się przypisy oznaczone jako „RPF”, które są uwagami wygłoszonymi przez Feynmana na wykładzie, a które w tekście najlepiej jest przenieść do przypisu. Przypisy oznaczone „przypis wydawcy” (w skrócie: przyp. wyd.) to komentarze wstawione przeze mnie i mojego współredaktora Robina Allena. W kilku miejscach zmieniłem również zapis Feynmana, aby dostosować go do obecnej praktyki, dotyczy to na przykład jego sposobu przedstawienia tranzystorów MOS.

Feynman nie uczył się przedmiotów w konwencjonalny sposób. Zazwyczaj kolega opowiadał mu o czymś, co go interesowało, a on później sam opracowywał szczegóły. Czasami dzięki temu procesowi Feynman był w stanie rzucić nowe światło na dany temat. Jego analiza obliczeń kwantowych jest tego przykładem, ale ilustruje również wady tej metody dla innych. W rozdziale na temat obliczeń kwantowych po wykazie literatury znajduje się przypis, który jest typowy dla Feynmana. Brzmi on: „Chciałbym podziękować T. Toffoliemu za pomoc przy bibliografii”. Dzięki swojej wyjątkowej wnikliwości i jasności myślenia Feynman często był w stanie nie tylko dokonać rzeczywistego postępu, ale także wyjaśnić podstawy całego problemu. W rezultacie praca Feynmana na temat obliczeń kwantowych jest powszechnie cytowana z pominięciem innych, mniej ważnych śmiertelników, którzy po drodze wnieśli istotny wkład. W tym przypadku często jest przywoływany Charles Bennett, ponieważ Feynman po raz pierwszy usłyszał o problemie od Bennetta, ale inni pionierzy, tacy jak Rolf Landauer i Paul Benioff, są pomijani. Ponieważ mocno wierzę, że Feynman nie chciał przypisywać sobie zasług innych, pozwoliłem sobie skorygować zapis historyczny w kilku miejscach i odesłać czytelnika w przypisie do bardziej kompletnych informacji na ten temat. Prawda była taka, że Feynman nie interesował się historią przedmiotu, a jedynie problemem, który miał być rozwiązany!

Z mojego redaktorskiego przywileju skorzystałem w jeszcze jeden sposób, mianowicie pomijając kilka wykładów na tematy, które stały się przestarzałe lub zostały wyparte w połowie lat 80. XX wieku. Aby jednak dać bardziej dokładne wyobrażenie o kursie, tym wykładom będzie towarzyszył tom, który zawiera artykuły na „zaawansowane tematy” napisane przez tych samych „ekspertów”, którzy uczestniczyli w tych kursach w CalTech. Ten uzupełniający tom będzie dotyczył postępu, jaki dokonał się w ciągu ostatnich dziesięciu lat[5] i będzie stanowił odpowiednie wspomnienie badań Feynmana w dziedzinie komputerów.

Po pomyślnym ukończeniu takiego projektu jak ten wielu osobom należą się słowa podziękowania. W szczególności powinienem podziękować Sandy’emu Freyowi i Erie Mjolness, którzy przede mną próbowali zaprowadzić porządek w tych notatkach. Jestem wdzięczny Geoffreyʼowi Foxowi za próbę odnalezienia studentów, którzy uczestniczyli w kursach, oraz Rodowi van Meterowi i Takako Matobie za przesłanie kopii ich notatek. Chciałbym również podziękować Getry’emu Sussmanowi i wyrazić wdzięczność zmarłemu Janowi van de Sneepscheut za ich początkową zachętę do podjęcia się tego zadania. Gerry był na CalTechu (na urlopie z MIT), kiedy Feynman zdecydował się działać sam, i pomagał mu w planowaniu kursu.

Starałem się, aby wszystkie błędy w (moim) rozumieniu zostały wyeliminowane z końcowej wersji tych wykładów. W tym zadaniu pomogło mi wiele osób. Rolf Landauer życzliwie przeczytał i poprawił rozdział 5 o obliczeniach odwracalnych i termodynamice oraz cierpliwie prowadził mnie przez historię tego tematu. Steve Furber, konstruktor procesora ARM RISC, a obecnie profesor na Uniwersytecie w Manchesterze, przeczytał i szczegółowo skomentował rozdział 7 o VLSI – zagadnieniu, o którym mam niewielką wiedzę z pierwszej ręki. Kilku moich kolegów z Southampton również bardzo pomogło mi w pracy nad tekstem: Adrian Pickering i Ed Załuska nad rozdziałami 1 i 2; Andy Gravell nad rozdziałem 3; Lajos Hanzo nad rozdziałem 4; Chris Anthony nad rozdziałem 5; a Peter Ashbum, John Hamel, Greg Parker i Ed Załuska nad rozdziałem 7. David Barron, Nick Barron i Mike Quinn z Southampton oraz Tom Knight z MIT byli uprzejmi przeczytać cały manuskrypt i dzięki ich uwagom usunięto wiele błędów i nieścisłości. Nie muszę dodawać, że biorę pełną odpowiedzialność za wszelkie pozostałe błędy i nieporozumienia! Muszę również podziękować Bobowi Churchhouse’owi z Cardiff University za informacje na temat szyfrów Bacona, Bobowi Nesbittowi z Southampton University za oświecenie mnie na temat geologa Williama Smitha oraz Jamesowi Davenportowi z Bath University za pomoc w znalezieniu bibliografii dotyczącej algorytmicznego rozwiązywania całek. Jestem również wdzięczny Optical Society of America za zgodę na przedrukowanie, w nieco zmienionej formie, klasycznego artykułu Feynmana z 1985 roku z Optics News na temat mechaniki kwantowej jako rozdziału 6 tych wykładów.

Po śmierci Feynmana bardzo pomogła mi jego żona Gweneth oraz przyjaciel rodziny Feynmanów, Dudley Wright, który wspierał mnie na wiele sposobów, miedzy innymi pomagając w opłaceniu transkrypcji taśm z wykładami. Muszę również złożyć wyrazy uznania mojemu współredaktorowi, Robinowi Allenowi, który pomógł mi wznowić projekt po rozstrzygnięciu długiego sporu o własność archiwum Feynmana, bez którego ten projekt nigdy nie ujrzałby światła dziennego. Wdzięczność należy się również Michelle Feynman, a także Carlowi Feynmanowi i jego żonie Pauli, którzy nieustannie wspierali ten projekt przez długie lata prawnego impasu i oferowali mi wszelką pomoc. Słowa podziękowania należą się Allanowi Wylde’owi, ówczesnemu dyrektorowi Advanced Book Program w Addison-Wesley, który okazał wielką wiarę w ten projekt w jego wczesnej fazie. Później Jeff Robbins i Heather Mimnaugh z Addison-Wesley Advanced Books wykazali się wzorową cierpliwością wobec nieuniknionych opóźnień i mojego irytującego uporu wobec pozornie nieistotnych szczegółów. Na koniec muszę wyrazić moją wdzięczność dla Helen Tuck za jej wiarę we mnie i przekonanie, że skończę tę pracę – przekonanie, które nie zawsze podzielałem! Mam nadzieję, że rezultat jej się spodoba.

Tony Hey

Wydział Elektroniki i Informatyki

Uniwersytetu w Southampton

Anglia

Maj 1996

Przedmowa Feynmana

Kiedy jakieś trzydzieści lat temu przygotowywałem książkę z moich wykładów, traktowałem ją jako pomoc dla studentów, którzy zamierzali zająć się fizyką. Narzekałem też na trudności związane z upchnięciem kilkusetletniego dorobku naukowego w trzech tomach. Z tymi wykładami na temat obliczeń sprawa jest nieco łatwiejsza, ale tylko trochę. Po pierwsze, wykłady nie są skierowane wyłącznie do studentów informatyki, co uwalnia mnie z kajdan egzaminacyjnych i pozwala na poruszanie się po związanych z tym zagadnieniach wyłącznie dlatego, że są interesujące. Po drugie, informatyka nie jest tak stara jak fizyka, jest późniejsza o kilkaset lat. Nie oznacza to jednak, że informatyk ma znacznie mniej do powiedzenia niż fizyk: może i jest młodszy, ale ma za sobą o wiele bardziej intensywne wychowanie! Jest więc jeszcze wiele do omówienia.

Informatyka różni się od fizyki także tym, że nie jest właściwie nauką. Nie zajmuje się badaniem obiektów naturalnych. Nie jest też, jak mogłoby się wydawać, matematyką, choć używa rozumowania matematycznego w dość szerokim zakresie. Informatyka jest raczej jak inżynieria – chodzi o to, by coś zrobić, a nie tylko zajmować się abstrakcjami, jak w geologii sprzed Smitha[6]. Dzisiaj w informatyce też trzeba „zejść do kopalni” – później możemy to uogólniać. Nie zaszkodzi jednak najpierw przyjrzeć się szczegółom.

Ale to nie znaczy, że informatyka jest praktycznym, przyziemnym budowaniem mostów. Daleko jej do tego. Informatyka dotyka wielu głębokich kwestii. Rozjaśniła naturę języka, który, jak nam się wydawało, rozumiemy: wczesne próby maszynowego tłumaczenia zawiodły, ponieważ staromodne pojęcia dotyczące gramatyki nie uchwyciły wszystkich istotnych cech języka. W naturalny sposób zachęca nas do zadawania pytań o granice obliczalności, o to, co możemy, a czego nie możemy wiedzieć o otaczającym nas świecie. Ludzie zajmujący się informatyką spędzają wiele czasu na dyskusjach o tym, czy człowiek jest tylko maszyną, czy jego mózg jest tylko potężnym komputerem, który pewnego dnia może zostać skopiowany, a dziedzina „sztucznej inteligencji” – ja wolę określenie „zaawansowane zastosowania” – może mieć wiele do powiedzenia na temat natury „prawdziwej” inteligencji i umysłu. Oczywiście możemy mieć pożyteczne pomysły, badając, jak działa mózg, ale musimy pamiętać, że samochody nie mają nóg jak gepardy, a samoloty nie machają skrzydłami! Nie musimy studiować neurologii żywych istot, by tworzyć użyteczne technologie, ale nawet błędne teorie mogą pomóc w projektowaniu maszyn. Tak czy inaczej, widać, że informatyka to coś więcej niż tylko technika.

Te wykłady są o tym, co możemy, a czego nie możemy dziś zrobić z maszynami i dlaczego. Starałem się wygłosić je w duchu, który należy polecić wszystkim studentom rozpoczynającym pisanie pracy doktorskiej: wyobraźcie sobie, że tłumaczycie swoje pomysły swojemu dawnemu ja – bystremu, ale ignorantowi, na początku studiów! W bardzo ogólnym zarysie, po krótkim wprowadzeniu do niektórych podstawowych idei, w następnych pięciu rozdziałach badam ograniczenia komputerów – od bramek logicznych do mechaniki kwantowej! Druga cześć składa się z wykładów zaproszonych ekspertów na temat tego, co nazwałem zaawansowanymi zastosowaniami – wizji, robotów, systemów eksperckich, maszyn szachowych i tak dalej[7].

1 Wprowadzenie do komputerów

Komputery mogą robić wiele rzeczy. Mogą dodawać miliony liczb w mgnieniu oka. Mogą przechytrzyć szachowych arcymistrzów. Mogą naprowadzić broń na cel. Mogą zarezerwować ci miejsce w samolocie między zakonnicą grającą na gitarze a niepalącym profesorem fizyki. Niektóre potrafią nawet grać na bongo. To całkiem spora różnorodność! Jeśli więc zamierzamy rozmawiać o komputerach, lepiej już teraz zdecydujmy, którym z nich się przyjrzymy i w jaki sposób.

W rzeczywistości nie będziemy poświęcać zbyt wiele czasu na przyglądanie się poszczególnym maszynom. Powodem tego jest to, że kiedy już wejdziemy do wnętrza komputerów, okazuje się, że podobnie jak ludzie, są one mniej lub bardziej do siebie podobne. Mogą różnić się funkcjami oraz naturą ich wejść i wyjść – jeden może tworzyć muzykę, a inny obraz, jeden może być uruchamiany z klawiatury, a inny przez moment obrotowy kół samochodu – ale w gruncie rzeczy są bardzo podobne. Dlatego też zajmiemy się tylko ich wnętrzem. Co więcej, nie będziemy zakładać niczego o ich specyficznej strukturze wejścia/wyjścia ( I/O ), o tym, jak informacja dostaje się do maszyny i z niej wychodzi. Obchodzi nas tylko to, że jakkolwiek dane dostają się do maszyny, są one w postaci cyfrowej, a cokolwiek dzieje się z wynikiem, ostatnie, co widzi jego wnętrze, jest również cyfrowe. Przez cyfrowe rozumiem tu liczby binarne, zapisane cyframi l i 0.

Jak wygląda wnętrze komputera? Najprościej rzecz ujmując, będzie ono zbudowane z zestawu prostych, podstawowych elementów. Elementy te nie są niczym szczególnym – mogą to być na przykład zawory sterujące lub koraliki na drucie liczydła – istnieje wiele możliwości wyboru podstawowego zestawu. Liczy się tylko to, że można z nich zbudować wszystko, co chcemy. Jak są one ułożone? I znów będzie wiele możliwych wyborów; odpowiednia struktura będzie prawdopodobnie określona przez takie czynniki jak prędkość, rozpraszanie energii, estetyka i jeszcze inne rzeczy. Patrząc na to w ten sposób, różnorodność komputerów jest trochę jak różnorodność domów: apartament w Beverly Hills może wydawać się zupełnie inny niż garaż w Yonkers, ale oba są zbudowane z tych samych rzeczy – cegieł, zaprawy, drewna, potu – tylko apartament ma ich więcej i są one różnie rozmieszczone w zależności od potrzeb właścicieli. W gruncie rzeczy są bardzo podobne.

Pozwólmy sobie na chwile abstrakcji i zapytajmy: w jaki sposób połączysz elementy jakiego zestawu, aby zrobić najwięcej rzeczy? To jest głębokie pytanie. Odpowiedź jest taka, że do pewnego momentu nie ma to znaczenia. Kiedy masz już komputer, który może zrobić kilka rzeczy – ściśle rzecz biorąc taki, który ma pewien „wystarczający zestaw” podstawowych procedur – może on zrobić w zasadzie wszystko, co może zrobić każdy inny komputer. To, swobodnie ujmując, jest podstawą wielkiej zasady „uniwersalności”. Och! – krzyczysz. Mój kieszonkowy kalkulator nie może symulować czerwonej plamy na Jowiszu jak grupa superkomputerów Cray! No, właśnie, może: wymagałoby to przerobienia okablowania, musielibyśmy podrasować jego pamięć i byłby cholernie wolny, ale gdyby miał wystarczająco dużo czasu, mógłby odtworzyć wszystko, co robią superkomputery. Ogólnie rzecz biorąc, załóżmy, że mamy dwa komputery A i B i wiemy wszystko o A – znamy sposób, w jaki działa, jego „reguły jego przejść między stanami” i co tam jeszcze. Załóżmy, że maszyna B jest w stanie jedynie opisać stan maszyny A. Możemy wtedy użyć B do symulowania działania A poprzez opisywanie jej kolejnych przejść. Innymi słowy, B będzie naśladować A. Może to zająć wieczność, jeśli B jest bardzo prymitywna, a A bardzo wyrafinowana, ale B będzie w końcu w stanie zrobić to co A. Udowodnimy to w dalszej części kursu, projektując taki komputer B, znany jako maszyna Turinga.

Spójrzmy na uniwersalność w inny sposób. Język stanowi użyteczne źródło analogii. Pozwólcie, że zapytam: jaki język jest najlepszy do opisania czegoś? Powiedzmy: czterokołowego pojazdu na benzynę. Oczywiście większość języków, przynajmniej na Zachodzie, ma na to proste słowo: my, Amerykanie, mamy „automobile”, Anglicy mówią „car”, Francuzi „voiture” i tak dalej. Będą jednak języki, które nie wykształciły słowa dla „samochodu”, a ich użytkownicy będą musieli wymyślić jakiś opis tego, co widzą, być może długi i złożony, wyrażony za pomocą podstawowych elementów języka. Jednak żaden z tych opisów nie jest z natury „lepszy” od pozostałych: wszystkie spełniają swoje zadanie i będą się różnić jedynie skutecznością. Nie musimy wprowadzać demokracji tylko na poziomie słów. Możemy zejść do poziomu alfabetów. Jaki jest na przykład najlepszy alfabet dla języka angielskiego? To znaczy, dlaczego trzymać się naszych zwyczajowych 26 liter? Wszystko, co możemy z nimi zrobić, można dokonać za pomocą trzech symboli jak w alfabecie Morse’a: kropki, kreski i spacji, lub dwóch jak w szyfrze Bacona, w którym litery od A do Z są reprezentowane przez pięciocyfrowe liczby binarne. Widzimy więc, że możemy wybrać nasz podstawowy zestaw elementów z dużą swobodą, a wszystko, na co ten wybór naprawdę wpływa, to efektywność naszego języka, a więc i na rozmiary naszych książek: nie ma „najlepszego” języka czy alfabetu – każdy z nich jest logicznie uniwersalny i każdy może wzorować się na każdym innym. Wracając do informatyki, uniwersalność oznacza faktycznie, że zbiór złożonych zadań, które mogą być wykonane przy użyciu „wystarczającego” zestawu podstawowych procedur, jest niezależny od konkretnej, szczegółowej struktury zestawu podstawowego.

Aby dzisiejsze komputery mogły wykonać złożone zadanie, potrzebujemy precyzyjnego i kompletnego opisu, jak wykonać to zadanie, w postaci sekwencji prostych procedur – „oprogramowania” – i potrzebujemy maszyny, która wykona te procedury w określonej kolejności – to jest „sprzętu”. Instrukcje muszą być dokładne i jednoznaczne. W życiu, oczywiście, nigdy nie mówimy sobie nawzajem dokładnie tego, co chcemy powiedzieć. Nigdy nie musimy tego robić, ponieważ kontekst, mowa ciała, znajomość mówiącego i tak dalej pozwalają nam „wypełniać luki” i rozwiązywać wszelkie niejasności w tym, co zostało powiedziane. Komputery jednak nie potrafią jeszcze „załapać”, co się do nich mówi, tak jak robi to człowiek. Trzeba im powiedzieć z drobiazgowymi szczegółami, co dokładnie mają zrobić. Być może pewnego dnia będziemy mieli maszyny, które poradzą sobie z przybliżonymi opisami zadań, ale tymczasem musimy w sposób bardzo sztywny nakazywać komputerom robienie różnych rzeczy.

Przyjrzyjmy się, jak możemy zbudować złożone instrukcje ze zbioru podstawowych elementów. Oczywiście, jeśli zbiór instrukcji B (powiedzmy) jest bardzo prosty, to złożony proces będzie wymagał bardzo szczegółowego opisu, a powstałe w ten sposób „programy” będą bardzo długie i skomplikowane. Możemy na przykład chcieć, aby nasz komputer wykonywał wszelkiego rodzaju obliczenia numeryczne, ale mamy zbiór B, który nie zawiera mnożenia jako odrębnego działania. Jeśli powiemy naszej maszynie, żeby pomnożyła 3 przez 35, to powie „co?”. Ale załóżmy, że B ma dodawanie. Jeśli się nad tym zastanowić, to można skłonić ją do mnożenia przez wielokrotne dodawanie – w tym przypadku należy wykonać dwukrotnie operację dodawania, najpierw dodając 35 do 35, a kolejne 35 dodając do uzyskanej sumy. Jeśli jednak rozszerzymy zbiór B o oddzielną instrukcję „pomnóż”, zdefiniowaną przez część podstawowych instrukcji B, które składają się na mnożenie, wyraźnie uprościmy pisanie programów w B. Wówczas, gdy zechcemy pomnożyć te dwie liczby, powiemy: „komputerze, 3 razy 35”, a on teraz rozpozna słowo „razy” – jest to po prostu dużo dodawania, które wykonuje. Maszyna dzieli te złożone instrukcje na ich podstawowe komponenty, oszczędzając nam ciągłego grzęźnięcia w pojęciach niższego rzędu. Złożone procedury są w ten sposób budowane krok po kroku. Bardzo podobny proces zachodzi w życiu codziennym; zastępujemy jednym słowem zbiór idei i powiązań między nimi. Odnosząc się do tych idei i ich wzajemnych powiązań, możemy wtedy użyć tylko jednego słowa i uniknąć konieczności wracania do wszystkich pojęć niższego poziomu. Komputery są tak skomplikowanymi obiektami, że upraszczające pomysły, takie jak ten, są zazwyczaj konieczne, a dobry projekt jest niezbędny, jeśli chcemy uniknąć całkowitego zagubienia się w szczegółach.

Zaczniemy od skonstruowania zbioru podstawowych procedur i sprawdzimy, jak wykonywać działania takie jak dodawanie dwóch liczb lub przenoszenie dwóch liczb z jednego magazynu pamięci do drugiego. Następnie przejdziemy o jeden poziom wyżej, do następnego rzędu złożoności, i użyjemy tych instrukcji do wykonania takich działań jak mnożenie i tak dalej. Nie zajdziemy zbyt daleko w tej hierarchii. Jeśli chcecie zobaczyć, jak daleko można się posunąć, zajrzyjcie do artykułu o systemach operacyjnych P.J. Denninga i R.L. Browna ( Scientific American, wrzesień 1984, str. 96–104) – autorzy określili w nim trzynaście poziomów! Począwszy od pierwszego poziomu, czyli obwodów elektronicznych – rejestrów, bramek, magistral – do trzynastego, czyli powłoki systemu operacyjnego, która steruje środowiskiem programistycznym użytkownika. Wskutek hierarchicznego łączenia instrukcji na pierwszym poziomie zachodzą podstawowe przełączenia jedynek na zera do momentu, gdy dotrzemy na poziom trzynasty, do poleceń pozwalających wylądować samolotem podczas symulacji lub sprawdzić, czy czterdziestocyfrowa liczba jest liczbą pierwszą. Wskoczymy do tej hierarchii na dość niskim poziomie, ale takim, z którego będziemy mogli iść w górę lub w dół.

Ponadto nasze rozważania będą ograniczone do komputerów o tak zwanej „architekturze Von Neumanna”. Nie zrażajcie się słowem „architektura” – jest to po prostu wielkie słowo oznaczające sposób, w jaki układamy rzeczy, tyle że układamy elementy elektroniczne, a nie cegły i słupy. Von Neumann był słynnym matematykiem, który oprócz tego, że wniósł ważny wkład w podstawy mechaniki kwantowej, był również pierwszym, który jasno określił podstawowe zasady działania współczesnych komputerów [8]. Będziemy też mieli okazję zbadać zachowanie kilku komputerów pracujących nad tym samym problemem, a kiedy to zrobimy, ograniczymy się do komputerów, które pracują sekwencyjnie, a nie równolegle, czyli takich, które rozwiązują na zmianę części problemu, a nie pracują jednocześnie. Wszystko, co możemy stracić przez pominięcie „przetwarzania równoległego”, to szybkość, ale to nic istotnego.

Mówiliśmy wcześniej o tym, że informatyka nie jest prawdziwą nauką. Teraz musimy również odrzucić słowo „komputer”! Otóż, słowo „komputer” [9] sprawia, że myślimy o arytmetyce – dodawaniu, odejmowaniu, mnożeniu i tak dalej – i łatwo jest założyć, że to wszystko, co robi komputer. W rzeczywistości konwencjonalne komputery mają jedno miejsce, w którym wykonują swoje podstawowe działania matematyczne, a reszta maszyny służy do wykonywania głównego zadania komputera, czyli przerzucania kawałków papieru – tylko w tym przypadku notatki na skrawkach papieru są cyfrowymi sygnałami elektrycznymi. Pod wieloma względami działanie komputera przypomina pracę urzędników biegających z papierkami tam i z powrotem do szafek na akta, wyjmujących je i wkładających z powrotem, bazgrzących na kawałkach papieru, przekazujących sobie notatki i tak dalej. Od tej metafory urzędnika przekładającego papiery w biurze zaczniemy przybliżać niektóre z podstawowych idei struktury komputera. Podejdziemy do tego szczegółowo – niecierpliwi mogą pomyśleć, że to zbyt szczegółowo, ale jest to doskonały model do opisania podstaw tego, co robi komputer, a zatem warto poświecić na to trochę czasu.

1.1. Model urzędnika archiwisty

Załóżmy, że mamy dużą firmę zatrudniającą wielu sprzedawców. Bardzo dużo informacji o tych sprzedawcach jest przechowywanych gdzieś w wielkim systemie archiwów, a wszystkim zarządza urzędnik. Zaczynamy od tego, że urzędnik wie, jak wydobyć informacje z systemu archiwizacji. Dane są przechowywane na kartach, a każda karta zawiera imię i nazwisko sprzedawcy, jego obszar działania, wielkość i rodzaj sprzedaży, jakiej dokonał, jego wynagrodzenie i tak dalej, i tak dalej.

Załóżmy teraz, że szukamy odpowiedzi na konkretne pytanie: „Jaka jest całkowita sprzedaż w Kalifornii?”. Jest dość nudne i proste i właśnie dlatego je wybrałem: trzeba zacząć od prostych pytań, aby później zrozumieć trudne. Jak więc nasz urzędnik znajdzie całkowitą sprzedaż w Kalifornii? Oto jeden ze sposobów, w jaki może to zrobić:

Wyjmij kartę

Jeśli „obszar działania” wskazuje Kalifornia, to

Dodaj liczbę w pozycji „sprzedaż” do bieżącego licznika o nazwie „razem”

Odłóż kartę „sprzedaż” na miejsce.

Wyjmij następną kartę i powtórz.

Oczywiście musisz to robić aż do momentu, gdy przejrzysz wszystkie karty. Załóżmy teraz, że mieliśmy pecha i zatrudniliśmy wyjątkowo głupich urzędników, którzy potrafią czytać, ale dla których powyższe instrukcje zakładają zbyt wiele: powiedzmy, że nie wiedzą, jak obsługiwać bieżący licznik. Musimy im trochę bardziej pomóc. Wymyślmy dla naszego urzędnika kartę „suma”. Będzie on jej używał do zapisywania bieżącej sumy w następujący sposób:

Wyjmij następną kartę „sprzedaż”

Jeśli Kalifornia, to

Wyjmij kartę „suma”

Dodaj liczbę określającą kwotę sprzedaży do liczby na karcie

Odłóż kartę „suma” na miejsce

Odłóż kartę „sprzedaż” na miejsce.

Wyjmij następną kartę „sprzedaż” i powtórz.

To jest bardzo mechaniczna ilustracja tego, jak prymitywny komputer mógłby rozwiązać ten problem dodawania. Oczywiście dane nie byłyby przechowywane na kartach, a maszyna nie musiałaby „wyjmować karty” – odczytywałaby zapisane informacje z rejestru. Mogłaby również zapisywać z rejestru na „kartę” bez fizycznego odkładania czegoś na miejsce.

Teraz będziemy „rozszerzać” naszego urzędnika! Załóżmy, że każdy sprzedawca otrzymuje od firmy nie tylko podstawową pensję, ale też jakąś prowizję od sprzedaży. Aby dowiedzieć się, ile ona wynosi, mnożymy jego sprzedaż przez odpowiedni procent. Chcemy, aby robił to nasz urzędnik. Jest on tani i szybki, ale niestety zbyt głupi, aby wykonać mnożenie[10]. Jeśli powiemy mu, żeby pomnożył 5 przez 7, powie „co?”. Musimy więc nauczyć go mnożyć. Aby to zrobić, wykorzystamy fakt, że jest jedna rzecz, którą robi dobrze: potrafi bardzo, bardzo szybko pobierać karty.

Będziemy korzystać z systemu o podstawie dwa. Jak zapewne wszyscy wiecie, reguły arytmetyki dwójkowej są prostsze niż dziesiętnej. Tabliczka mnożenia jest tak mała, że z łatwością zmieści się na jednej kartce. Założymy, że nawet nasz urzędnik może je zapamiętać; wszystko, czego potrzebuje, to operacje „przesuń” i „przenieś”, jak pokazuje poniższy przykład:

Tak więc dopóki nasz urzędnik potrafi przesuwać i przenosić, może w istocie mnożyć. Robi to bardzo głupio, ale też bardzo szybko, i o to w tym wszystkim chodzi: wnętrze komputera jest głupie jak diabli, ale działa jak szalone! Może wykonywać bardzo wiele milionów prostych działań na sekundę i jest jak bardzo szybki, tępy urzędnik. Tylko dlatego, że jest w stanie robić rzeczy tak szybko, nie zauważamy, że robi to bardzo głupio. (Co ciekawe, neurony w mózgu potrzebują milisekund na wykonanie elementarnych operacji, co pozostawia nas z zagadką, dlaczego mózg jest taki mądry? Komputery mogą zostawić mózgi w tyle, jeśli chodzi o mnożenie, ale mają problemy z rzeczami, które nawet małe dzieci uważają za proste, jak rozpoznawanie ludzi czy manipulowanie przedmiotami).

Aby pójść dalej, musimy dokładniej określić nasz podstawowy zestaw działań (operacji). Jednym z najbardziej elementarnych jest przenoszenie informacji z kart, które czyta nasz urzędnik, na coś w rodzaju notatnika, w którym może on wykonywać swoje działania arytmetyczne:

Działania przenoszenia

„Weź kartę X” = Informacja na karcie X zapisana w notatniku

„Zastąp kartę Y” = Informacja w notatniku zapisana na karcie Y

Wszystkim, co zrobiliśmy, jest zdefiniowanie instrukcji „weź kartę X”, która oznacza kopiowanie informacji z karty X do notatnika, i podobnie z „zastąp kartę Y”. Następnie chcemy być w stanie poinstruować urzędnika, aby sprawdził, czy obszar działania na karcie X to „Kalifornia”. Musi on to zrobić dla każdej karty, więc pierwszą rzeczą, jaką ma zrobić, jest pamiętanie wartości „Kalifornia” od jednej karty do drugiej. Jednym ze sposobów, aby mu w tym pomóc, jest zapisanie Kalifornia na jeszcze jednej karcie, C, tak że jego instrukcje wyglądają teraz następująco:

Weź kartę X (z magazynu do notatnika)

Weź kartę C (z magazynu do notatnika)

Porównaj to, co jest na karcie X, z tym, co jest na karcie C.

Następnie mówimy mu, że jeśli zawartość się zgadza, to zrób tak i tak, a jeśli nie, to odłóż karty z powrotem i weź następne. Ciągłe wyjmowanie i odkładanie karty Kalifornia wydaje się trochę nieefektywne i rzeczywiście nie trzeba tego robić. Można zamiast tego trzymać ją przez jakiś czas w notatniku. Byłoby to lepsze rozwiązanie, ale wszystko zależy od tego, ile miejsca urzędnik ma swoim notatniku i ile fragmentów informacji musi zachować. Jeśli nie ma zbyt wiele miejsca, to będzie dużo przekładania kartek w tę i z powrotem. Musimy się martwić takimi sprawami!

Możemy dalej rozkładać skomplikowane zadania urzędnika na prostsze, bardziej podstawowe. Jak na przykład skłonić go do spojrzenia na część „obszar działania” na karcie z magazynu? Jednym ze sposobów byłoby obarczenie biedaka jeszcze jedną kartą, na której jest napisane coś takiego:

0000 0000 0000 0000 0000 1111 0000 0000 0000 0000…

Każdy ciąg cyfr jest powiązany z określoną informacją na karcie: pierwszy ciąg zer oznacza nazwisko sprzedawcy, następny, powiedzmy, jego wiek i tak dalej. Urzędnik przegląda tę listę liczb, aż trafi na ciąg jedynek, a następnie odczytuje informacje znajdujące się obok nich. W naszym przypadku 1111 oznacza Kalifornię. Tego rodzaju procedura lokalizacji jest w rzeczywistości używana w komputerach, gdzie można użyć tak zwanej operacji „iloczynu bitowego” (omówimy to później). Ta mała dygresja miała na celu uzmysłowienie, że nie musimy brać umiejętności naszego urzędnika za pewnik – możemy skłonić go do robienia coraz głupszych rzeczy.

1.2. Zbiory instrukcji

Przyjrzyjmy się notatnikowi urzędnika. Nie nauczyliśmy jeszcze urzędnika, jak z niego korzystać, więc zrobimy to teraz. Przyjmiemy, że możemy podzielić instrukcje, które może on wykonywać, na dwie grupy. Po pierwsze, istnieje podstawowy „zestaw instrukcji” złożony z prostych procedur, które są dostarczane z notatnikiem – dodawanie, przenoszenie itd. Są one w sprzęcie: nie zmieniają się, gdy zmieniamy problem. Odzwierciedlają podstawowe umiejętności urzędnika. Następnie mamy zestaw, który jest charakterystyczny dla danego zadania, powiedzmy obliczania prowizji sprzedawcy. Elementy tego zestawu są zbudowane z instrukcji z zestawu podstawowego w sposób, który już omówiliśmy, i reprezentują kombinację talentów urzędnika, które będą od niego wymagane w celu wykonania zadania.

Pierwszym naszym zadaniem jest sprawienie, aby urzędnik robił rzeczy we właściwej kolejności, to znaczy, aby wykonywał instrukcje zgodnie z ich kolejnością. Dokonujemy tego, wyznaczając jeden z obszarów pamięci w notatniku na „licznik programu”. Będzie on zawierał liczbę wskazującą, w którym miejscu procedury obliczeniowej znajduje się urzędnik. Dla urzędnika liczba ta jest adresem – wie on, że w systemie plików jest zakopana specjalna szafka z „kartoteką instrukcji”, a liczba w liczniku oznacza w tej kartotece kartę, po którą musi pójść i ją wziąć. Na karcie jest instrukcja, co ma dalej robić. Otrzymuje więc instrukcję i zapisuje ją w swoim notatniku w miejscu, które nazywamy „rejestrem instrukcji”.

Zanim jednak wykona instrukcję, przygotowuje się do wykonania następnej, zwiększając wartość w liczniku programu. Robi to, po prostu dodając do niej jeden. Następnie wykonuje to, co nakazuje mu instrukcja w rejestrze. Używając notacji z nawiasami, w której ( ) oznacza „zawartość” – zapamiętajcie tę konwencję, bo będziemy jej często używać – możemy zapisać sekwencję działań w następujący sposób[11]:

Pobierz instrukcję z adresu PC

PC ← ( PC) + 1

Wykonaj instrukcję

Drugi wiersz jest wymyślnym sposobem powiedzenia, że licznik PC „otrzymuje” nową wartość ( PC) + l. Urzędnik będzie również potrzebował w notatniku kilku tymczasowych miejsc na przechowywanie, na przykład, aby umożliwić mu wykonywanie operacji arytmetycznych. Są to tzw. rejestry, które zapewniają mu miejsce do przechowania czegoś, podczas gdy on idzie i znajduje inną liczbę. Nawet jeśli dodajecie tylko dwie liczby, trzeba zapamiętać pierwszą, dopóki nie pobierzecie drugiej! Wszystko musi być zrobione po kolei, a rejestry umożliwiają nam uporządkowanie tych spraw. Zazwyczaj rejestry mają nazwy. W naszym przypadku będziemy mieli cztery rejestry. Nazwiemy je A, B, X i C. Czwarty rejestr jest specjalny, ponieważ może przechowywać tylko jeden bit danych. Będziemy go nazywać rejestrem „przenoszenia”. Może być więcej lub mniej rejestrów – generalnie im więcej, tym łatwiej napisać program – ale do naszych celów wystarczą cztery.

Nasz urzędnik wie więc, jak się dowiedzieć, co i kiedy ma zrobić. Przyjrzyjmy się teraz podstawowemu zestawowi instrukcji dla jego notatnika. Pierwszy rodzaj instrukcji dotyczy przenoszenia danych z jednej karty na drugą. Załóżmy na przykład, że mamy w notatniku miejsce pamięci M. Chcemy mieć instrukcję, która przeniesie zawartość rejestru A do M:

Przenieś ( A ) do M    lub    M ← ( A )

Podobnie możemy chcieć wykonać działanie przeciwne i zapisać zawartość M do A:

Przenieś ( M) do A    lub    A ← ( M)

Nawiasem mówiąc, M niekoniecznie jest przeznaczone do tymczasowego przechowywania jak A. Musimy również mieć analogiczne instrukcje dla rejestru B:

Przenieś ( B ) do M    lub    M ← ( B )

Przenieś ( M) do B    lub    B ← ( M)

Z rejestru X będziemy korzystać nieco inaczej. Zezwolimy na przenoszenie z B do X i z X do B:

X ← ( B ) i  B ← ( X).

Musimy mieć ponadto możliwość śledzenia i manipulowania naszym licznikiem programu PC. Jest to oczywiście konieczne: jeśli urzędnik odejdzie, by wykonać, powiedzmy, mnożenie, to po powrocie musi wiedzieć, co robić dalej – musi pamiętać liczbę w PC. W istocie będziemy ją trzymać w rejestrze X. Dodajemy więc instrukcje przeniesienia:

PC ← ( X) i  X ← ( PC).

Następnie potrzebne są operacje arytmetyczne i logiczne. Najbardziej podstawową z nich jest instrukcja „wyczyść”:

Wyczyść A, czyli A ← 0.

Oznacza to, że cokolwiek jest w A, zapomnij o tym, wymaż to. Następnie potrzebujemy operacji sumowania:

Dodaj B do A, czyli A ← ( A ) + ( B )

Oznacza to, że do rejestru A trafia suma zawartości rejestru B i poprzedniej zawartości A. Mamy też operację przesunięcia, dzięki której będziemy mogli wykonywać mnożenie bez konieczności wprowadzania dla niego instrukcji podstawowej:

Przesuń A w lewo i  Przesuń A w prawo

Pierwsza z nich po prostu przesuwa wszystkie bity w A o jedno miejsce w lewo. Jeśli to przesunięcie spowoduje nadmiar dla lewego skrajnego bitu, to przechowujemy go w rejestrze przeniesienia C. Możemy też przesunąć naszą liczbę w prawo. Nie mam na myśli żadnego zastosowania, ale może się przydać!

Kolejne instrukcje są instrukcjami logicznymi. Przyjrzymy się im bardziej szczegółowo w następnym rozdziale, ale wspomnę o nich tutaj dla spójności wykładu. Są trzy rodzaje instrukcji, które nas interesują: AND, OR i XOR. Każda z nich jest funkcją dwóch „wejść” cyfrowych x i y. Jeśli oba wejścia mają wartość 1, to AND daje 1, a w przeciwnym razie daje zero. Jak zobaczymy, operacja AND pojawia się w dodawaniu binarnym, a więc i mnożeniu. Jeśli potraktujemy x i y jako dwie dodawane do siebie cyfry, to ( x AND y) jest bitem przeniesienia: ma on wartość jeden tylko wtedy, gdy obie cyfry mają wartość jeden. W przypadku naszych rejestrów, x i y to ( A ) i ( B ), a AND wykonuje na nich działania:

AND: A ← ( A ) ∧ ( B ),

gdzie użyliśmy symbolu logicznego ∧ dla operacji AND. Wynik działania na parze zmiennych za pomocą operatora takiego jak AND jest często przedstawiany w „tablicy prawdy” (tabela 1.1).

Tabela 1.1. Tablica prawdy dla operatora AND

Nasze pozostałe dwa operatory mogą być opisane w podobny sposób. OR również działa na ( A ) i ( B ). Daje jedynkę, chyba że ( A ) i ( B ) są zerami – (x OR y) jest jedynką, jeśli x lub y jest jedynką. XOR, czyli alternatywa wykluczająca (exclusive or), jest podobna do OR, z tym że daje też zero, jeśli zarówno ( A ), jak i ( B ) są jedynkami. W binarnym dodawaniu x i y działanie to odpowiada temu, co otrzymamy, jeśli dodamy x do y i pominiemy bity przeniesienia. W binarnym dodawaniu 1 plus 1 jest równe 10, co jest zerem, jeśli zapomnimy o przeniesieniu. Możemy wprowadzić odpowiednie symbole logiczne:

OR A ← ( A ) ∨ ( B )

XOR A ← ( A ) ⊕ ( B )

Operacje OR oraz XOR można również przedstawić za pomocą tablic prawdy:

Tabela 1.2. Tablice prawdy dla operatorów OR i XOR

Dwie kolejne operacje, którymi warto dysponować, to instrukcja inkrementacji lub dekrementacji zawartości A (czy zwiększenia jej lub zmniejszenia o jeden):

Inkrementuj A, czyli A ← ( A ) + 1

Dekrementuj A, czyli A ← ( A ) – 1

Przypisy

[1] Richard Feynman zmarł 15 lutego 1988 roku (przyp. red.).

[2] Wydane ostatnio (2021 r.) przez Społeczny Instytut Wydawniczy Znak; wcześniej w roku 1996 (przyp. tłum.).

[3] W oryginale: „Potentialities and Limitations of Computing Machines” (przyp. red.).

[4] Wygłoszono je w 1986 roku (przyp. red.).

[5] Mowa o ostatnim dziesięcioleciu XX wieku (przyp. red.).

[6] Wiliam Smith był ojcem współczesnej geologii; w swojej pracy jako inżynier, specjalista od budowy kanałów i górnictwa, badał proces tworzenia skał i docenił znaczenie skamieniałości jako sposobu wyznaczania wieku warstwy, w której występują. W ten sposób sformułował zasadę nakładania, według której skały sukcesywnie układają się na starszych warstwach. Przed wielkim wkładem Smitha geologia przypominała bardziej starą gabinetową filozofię niż naukę empiryczną (przyp. wyd.).

[7] Tom towarzyszący tym wykładom jest w przygotowaniu. Na ile to możliwe, ten drugi tom będzie zawierać artykuły o „zaawansowanych zastosowaniach” pisane przez tych samych ekspertów, który współtworzyli kurs Feymana, lecz uaktualnionych, aby odzwierciedlić obecny stan wiedzy (przyp. wyd.).

[8] Obecnie jest duże zainteresowanie projektowaniem maszyn „nie-Von Neumanna”. Zostanie to omówione przez zaproszonych „ekspertów”, w tomie towarzyszącym książce (przyp. wyd.).

[9] Słowo komputer pochodzi od łacińskiego czasownika computare, który oznacza obliczyć, sumować, liczyć (przyp. tłum.).

[10] Tak na marginesie, chociaż w tych przykładach zakłada się, że tępy archiwista jest mężczyzną, nie ma w tym żadnych uprzedzeń związanych z płcią (RPF).

[11] Konwencje przyjęte dla takiego „języka przeniesienia rejestrów” różnią się zależnie od kaprysów ich autora. Tutaj wybraliśmy tak zwaną konwencję „od prawej do lewej” stosowaną w standardowych językach programowania (przyp. wyd.).