функция маккарти (немного математики)

[avva]

Мне раньше не встречалась эта забавная функция.

Определение (рекурсивное):

• g(x) = x-10 если x > 100
• g(x) = g(g(x+11)) если x <= 100

g(x) называется 91-функцией Маккарти. Поведение g(x) для x>100 тривиально, как следует из первой строки определения; поведение для x<=100 на первый взгляд неочевидно.

Доказать: g(x)=91 для x<=101.

Я не предлагаю это в качестве задачи для решения в комментах, потому что доказать это очень легко, но все-таки надо немного подумать. Просто красиво, по-моему, и я хотел этим небольшим кусочком красоты, о котором сегодня случайно узнал, поделиться.

Comments

[ygam.livejournal.com]

g(100) = g(g(111)) = g(101) = 91
g(99) = g(g(110)) = g(100) = 91
g(98) = g(g(109)) = g(99) = 91
...
g(90) = g(g(101)) = g(91) = 91
g(89) = g(g(100)) = g(91) = 91
g(88) = g(g(99)) = g(91) = 91
...

Действительно красиво. Я где-то тоже раньше видел определение этой функции - у Дюдни в The Turing Omnibus, что ли?

[russian-bob.livejournal.com]

Хороший пример того как простое можно сделать сложным.
Ну правда, зачем нужна эта функция?

Можно было написать:
g(x) = x-10, for x >= 101
g(x) = 91, for x < 101

И это работает для всех х, целых и дробных.

[aburachil.livejournal.com]

Осталось лишь понять, почему у этой функции есть имя. Х-м-м-м... Вот в чём задача-то!

[russian-bob.livejournal.com]

Маккарти тоже человек, у него семья, наверное, дети.

[malaya-zemlya.livejournal.com]

http://en.wikipedia.org/wiki/John_McCarthy_%28computer_scientist%29

[russian-bob.livejournal.com]

Теперь я за него спокоен.

[aburachil.livejournal.com]

Интересно, сколько он получает патентных сборов.

[sam0g0n.livejournal.com]

ты бы пивка бы выпил.... расслабился......

[azzo27.livejournal.com]

Верно, если x целое.
Для нецелых x<101 g(x) = 90 + Дробная_часть(x)

[russian-bob.livejournal.com]

это даже похоже не непрерывная функция, т.е. для х<=100 она будет выглядеть как пила, меняя скачком своё значемие с 90.99(9) на 90 когда х пересекает целое значение.

[azzo27.livejournal.com]

Да, конечно.
Ваш юзерпик похож на мои стародавние фотографии :))

[russian-bob.livejournal.com]

Значит родственники. :)

[azzo27.livejournal.com]

А откуда Вы родом?

[russian-bob.livejournal.com]

Я москвич, но насчёт родственников - все мы родственники, хотя бы по Адаму. :)

Я - семит, и рожа моя - семитская, таких в ЖЖ полно. Вот например, gottfrid тоже похож. Можем уже клуб такой организовывать.
На Вас я похож пожалуй только на этой фотографии, но всё равно, приятно познакомится. :)

PS: Насчёт "стародавности" ваших фото, судя по userinfo, Вы меня лет на 5-6 старше, отсилы.

[azzo27.livejournal.com]

Да я тоже не ариец. Дедушка у меня был с Зап.Украины, а бабушка из Литвы, познакомились они в Горьком. А я родился в Свердловске. В 1954-м.

[russian-bob.livejournal.com]

Верно, но только для целых х.
Если х дробное число, это правило не работает:

g(100.67) = 100.67 - 10 = 90.67
g(99.5) = g(g(99.5+11)) = g(g(110.5)) = g(100.5) = 90.5

[yakov-a-jerkov.livejournal.com]

Хорошая задача. Но только для целых x, как уже отметили.

Правда, я, признаюсь, про нецелые x вообще не подумал, пока комментарии не посмотрел.

[moon-aka-sun.livejournal.com]

Чего красивого? Вот оператор фиксированной точки - это да. Не понятно даже как и почему работает, но работает.

Например, нерекурсивный факториал на Питоне:

# function closures are powerful
# lambdas w/o lambdas :)

# traditional fixed-point operator from functional programming
def Y(g):
  def a(p):
    return p(p)
  def z(f):
    def b(x):
      return f(f)(x)
    return g(b)
  return a(z)

# factorial without recursion
def F(f):
  def u(n):
    if n==0: return 1
    else: return n*f(n-1)
  return u

factorial = Y(F) # factorial is the fixed point of F

# now test it
def test(x):
  print "%d! = %d" % (x,factorial(x))

for n in range(18):
  test(n)

Или на К:

Y:{[t]{x[x]}[{[f]t[{f[f][x]}]}]} / fixed-point operator
F:{[f]{:[x=0;1.0;x*f[x-1]]}} / factorial without recursion
factorial:Y[F] / factorial is the fixed point of F
test:{($x),"!=",($factorial[x]),"\n"} / test function
\p 15 / set output precision to 15 digits (we deal with floats)
`0:,/test'!18 / just do it!

(На Хаскелле, наверное, тоже похоже будет.)

[ex-n-n710.livejournal.com]

неподвижной точки?

[moon-aka-sun.livejournal.com]

Может быть. Я по-русски не знаю. И по-английски-то не очень.

[avva.livejournal.com]

Ну, не так уж непонятно :)

[freeborn.livejournal.com]

это, конечно, смешно, но на javascript оно тоже работает %) function Y(g) { var a = function(p) { return p(p); }; var z = function(f) { var b = function(x) { return f(f)(x); }; return g(b); }; return a(z); } function F(f) { var u = function(n) { return n == 0 ? 1 : n * f(n-1); }; return u; } var fact = Y ( F );