Нашою метою в цій главі буде дослідження можливостей комп'ютерів. Ми хочемо зрозуміти, що машини можуть зробити, а що не можуть, і що потрібно машинам, щоб продемонструвати максимум здібностей. Почнемо з концепції обчислювальних функцій (computing functions).
У математичному сенсі функція - це відповідність між набором можливих вхідних значень і набором вихідних значень, причому кожен можливий вхід пов'язаний з унікальним результатом. Як приклад можна привести функцію перетворення ярдів в метри. Для кожної дистанції в ярдів функція видасть унікальне значення, яке вийде при вимірюванні того ж відстані в метрах. Інший приклад, який ми можемо назвати функцією сортування, ставить у відповідність кожному вхідному списку вихідний список, який містить ті ж елементи, що і вхідний список, але організовані вони відповідно до деякого наперед визначеним правилом. І ще один приклад - функція складання, входами для якої є пари значень, а виходами - значення, що є сумами вхідних пар.
Процес визначення вихідного значення, яке функція ставить у відповідність даного входу, називається обчисленням функції. Здатність обчислювати функції дуже важлива, оскільки саме це ми робимо при вирішенні завдань. Для вирішення завдання складання необхідно виконати функцію додавання; для сортування списку виконується функція сортування. У свою чергу, фундаментальної завданням обчислювальної техніки є пошук методів обчислення функцій, що лежать в основі проблем, які ми хочемо вирішити.
Розглянемо, наприклад, систему, в якій входи і виходи функції можуть бути заздалегідь визначені і занесені в таблицю. Кожен раз, коли нам потрібно вихід функції, ми просто шукаємо в таблиці потрібний вхід і відповідний йому вихід. Так, обчислення функції можна звести до процесу пошуку в таблиці. Подібні системи зручні, але їх можливості обмежені, оскільки величезна кількість функцій не представимо в табличній формі. Приклад цього наведено на рис. 11.1, де ми спробували показати функцію перетворення ярдів в метри. Так як список можливих пар входів і виходів не обмежений, таблиця ніколи не буде завершена.
Більш розумний підхід до обчислення функції - виконувати дії відповідно до алгебраїчної формулою замість того, щоб намагатися звести всі можливі комбінації входів і виходів в таблицю. Наприклад, за допомогою алгебраїчної формули
ми можемо описати величину V, яка була збільшилася відповідно з річною ставкою відсотка г за і років значення вихідних інвестицій Р. Але виразні можливості алгебраїчних формул також обмежені. Існують функції, відносини між входами і виходами яких занадто складні для того, щоб їх можна було описати алгебраїчними діями. Наприклад, тригонометричні функції, такі як синус і косинус. Якщо вам потрібно обчислити синус 38 градусів, ви можете намалювати відповідний трикутник, виміряти його боку і порахувати потрібне співвідношення - такий процес неможливо виразити в термінах алгебраїчних дій зі значенням 38. Ваш кишеньковий калькулятор також не вміє обчислювати синус 38 градусів. Насправді він застосовує складні математичні методи для отримання дуже хорошого наближення синуса 38 градусів, яке і видає вам в якості відповіді.