?

Log in

функция маккарти (немного математики) - Поклонник деепричастий [entries|archive|friends|userinfo]
Anatoly Vorobey

[ website | Website ]
[ userinfo | livejournal userinfo ]
[ archive | journal archive ]

Links
[Links:| English-language weblog ]

функция маккарти (немного математики) [окт. 10, 2006|02:48 am]
Anatoly Vorobey

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

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

  • 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:
[User Picture]From: ygam
2006-10-10 01:00 am
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, что ли?
(Ответить) (Thread)
[User Picture]From: russian_bob
2006-10-10 01:27 am
Хороший пример того как простое можно сделать сложным.
Ну правда, зачем нужна эта функция?

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

И это работает для всех х, целых и дробных.
(Ответить) (Parent) (Thread)
[User Picture]From: aburachil
2006-10-10 08:15 am
Осталось лишь понять, почему у этой функции есть имя. Х-м-м-м... Вот в чём задача-то!
(Ответить) (Parent) (Thread)
[User Picture]From: russian_bob
2006-10-10 12:49 pm
Маккарти тоже человек, у него семья, наверное, дети.
(Ответить) (Parent) (Thread)
[User Picture]From: russian_bob
2006-10-10 04:05 pm
Теперь я за него спокоен.
(Ответить) (Parent) (Thread)
[User Picture]From: aburachil
2006-10-10 10:12 pm
Интересно, сколько он получает патентных сборов.
(Ответить) (Parent) (Thread)
[User Picture]From: sam0g0n
2006-10-10 01:00 am
ты бы пивка бы выпил.... расслабился......
(Ответить) (Thread)
[User Picture]From: azzo27
2006-10-10 01:18 am
Верно, если x целое.
Для нецелых x<101 g(x) = 90 + Дробная_часть(x)
(Ответить) (Thread)
[User Picture]From: russian_bob
2006-10-10 01:36 am
это даже похоже не непрерывная функция, т.е. для х<=100 она будет выглядеть как пила, меняя скачком своё значемие с 90.99(9) на 90 когда х пересекает целое значение.
(Ответить) (Parent) (Thread)
[User Picture]From: azzo27
2006-10-10 01:41 am
Да, конечно.
Ваш юзерпик похож на мои стародавние фотографии :))
(Ответить) (Parent) (Thread)
[User Picture]From: russian_bob
2006-10-10 01:50 am
Значит родственники. :)
(Ответить) (Parent) (Thread)
[User Picture]From: azzo27
2006-10-10 02:52 am
А откуда Вы родом?
(Ответить) (Parent) (Thread)
[User Picture]From: russian_bob
2006-10-10 12:40 pm
Я москвич, но насчёт родственников - все мы родственники, хотя бы по Адаму. :)

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

PS: Насчёт "стародавности" ваших фото, судя по userinfo, Вы меня лет на 5-6 старше, отсилы.
(Ответить) (Parent) (Thread)
[User Picture]From: azzo27
2006-10-10 06:03 pm
Да я тоже не ариец. Дедушка у меня был с Зап.Украины, а бабушка из Литвы, познакомились они в Горьком. А я родился в Свердловске. В 1954-м.
(Ответить) (Parent) (Thread)
[User Picture]From: russian_bob
2006-10-10 01:23 am
Верно, но только для целых х.
Если х дробное число, это правило не работает:

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
(Ответить) (Thread)
[User Picture]From: yakov_a_jerkov
2006-10-10 01:37 am
Хорошая задача. Но только для целых x, как уже отметили.

Правда, я, признаюсь, про нецелые x вообще не подумал, пока комментарии не посмотрел.
(Ответить) (Thread)
[User Picture]From: moon_aka_sun
2006-10-10 03:30 am
Чего красивого? Вот оператор фиксированной точки - это да. Не понятно даже как и почему работает, но работает.

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

# 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!

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

(Ответить) (Thread)
From: ex_n_n710
2006-10-10 05:46 pm
неподвижной точки?
(Ответить) (Parent) (Thread)
[User Picture]From: moon_aka_sun
2006-10-10 05:53 pm
Может быть. Я по-русски не знаю. И по-английски-то не очень.
(Ответить) (Parent) (Thread)
[User Picture]From: avva
2006-10-10 05:50 pm
Ну, не так уж непонятно :)
(Ответить) (Parent) (Thread)
[User Picture]From: freeborn
2006-10-11 03:15 am
это, конечно, смешно, но на 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 );
(Ответить) (Parent) (Thread)